题解 | #两数之和#
两数之和
https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f
方法一：暴力破解法，使用两个for循环相加 看是否等于目标值，简单直观 便于理解。但是空间时间复杂度过高，部分用例超时没有通过。
public int[] twoSum (int[] numbers, int target) {
// write code here
int[] res = new int[2];
for (int i = 0; i < numbers.length; i++) {
for (int j = i+1; j < numbers.length; j++) {
if (i != j && numbers[i] + numbers[j] == target) {
res[0] = i+1;
res[1] = j+1;
}
}
}
return res;
}
方法二 hash表
具体做法：
使用Map来降低时间复杂度，遍历数组，如果没有 （target - 当前值） 就将当前数字存入哈希表，如果有，返回该数字下标即可。
public int[] twoSum (int[] numbers, int target) {
// write code here
HashMap<Integer,Integer> hashMap = new HashMap();
int[] res = new int[2];
for (int i = 0; i < numbers.length; i++) {
if (hashMap.containsKey(numbers[i])) {
res[0] = hashMap.get(numbers[i]) + 1;
res[1] = i + 1;
} else {
hashMap.put(target-numbers[i] ,i);
}
}
return res;
}
查看15道真题和解析
