题目描述
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。
你可以假设只有一组答案。
思路
因为要找两数之和等于target，但数组未排序，显然如果暴力查找时间复杂度太大
给数组排序后可以很容易找到两数之和等于target，但新问题是：排序会打乱原来元素的顺序，就无法得到这两个数在原数组准确的下标了。
综上，可以这么处理：
- 用一个hashmap保存该数组，key为下标+1，value就是数组的值
- 数组排序
- 找到这两个数
- 自己写一个通过value找到key的函数，输出下标
通过value找key也很容易，通过keyset集可以轻松遍历map里的value，比较相等后将key添加到int[]数组即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
int tmpIndex = 1;
for(int num : numbers) {
hashMap.put(tmpIndex++, num);
}
Arrays.sort(numbers);
int i = 0;
int j = numbers.length-1;
while(i < j) {
if(target < numbers[i]+numbers[j]) {
j--;
}else if (target > numbers[i]+numbers[j]) {
i++;
}else {
return getKey(hashMap, numbers[i], numbers[j]);
}
}
return new int[]{};
}
private int[] getKey(HashMap<Integer, Integer> hashMap, int value1, int value2) {
int[] res = new int[2];
int i = 0;
Set<Integer> keySet = hashMap.keySet();
for(int key : keySet) {
if(hashMap.get(key) == value1 || hashMap.get(key) == value2) {
res[i++] = key;
}
}
return res;
}
|
考察点