05 August 2008
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Leetcode的第一道题，被翻来覆去做过很多遍了；一般就是HashMap存入值和相对应index的信息，回过来再对之前存入的键值对进行查找。
Time: O(n), Space: O(n);
另外还有一个办法是可以先对数组排序，然后用两个指针，头尾开始查找，直到找到结果或者两个指针相遇。因为Arrays.sort()使用的排序方法是quick sort和优化过的merge sort，为什么使用了两种排序方法？《Java编程艺术》上的解释是quick sort对基本数据类型包括int，short，long，float，double等的排序，merge sort则是对对象类型进行排序，对比下两个排序办法：
1
2
3
4
5
6
7
8
merge sort
1）最坏时间复杂度是 O(nlogn)；
2）平均时间复杂度是 O(nlogn)；
3）空间复杂度如果用Array实现为O(n),如果用LinkedList来实现为O(logn)。
quick sort
1）最坏时间复杂度是 O(n^2)；
2）平均时间复杂度是 O(nlogn)；
3）空间复杂度是 O(n)。
因此，这个办法的时间复杂度Arrays.sort()的O(nlogn)+后面两个指针的的O(n) = O(nlogn)；另外因为本题是返回两个indices，而不是返回两个值，所以还需要记住之前每个元素的位置，复制一个数组（延伸：Java中常用有几种复制数组的办法？）进行排序，原数组则保持原来顺序。
扩展下知识：quick sort 在统计意义上效率比 merge sort 高，为何不都采用 quick sort ？
使用两个不同类型的排序算法主要是由于 quick sort 是不稳定的，而 merge sort 是 稳定（stable）的。这里的 stable 是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列（保序性）。对于基本数据类型，稳定性没有意义。而对于对象类型，稳定性比较重要，因为对象相等的判断可能只是判断关键属性，因此最好保持相等对象的非关键属性的顺序与排序前一直；另外一个原因是由于merge sort相对而言比较（compare）的次数比快速排序要少，移动（对象引用的移动，move）次数比快速排序多，而对于对象来说，compare一般比move耗时。
HashMap的办法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
//注意存到result的顺序
result[1] = i;//第1位为当前的i
result[0] = map.get(target - nums[i]);//第0位为跟当前i匹配之前存入到map中的值和相对应的index
break;
}
map.put(nums[i], i);//值和其相对应的index
}
return result;
}
}
两个指针的办法
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
33
34
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] sorted = new int[nums.length]; //一个新数组来排序
System.arraycopy(nums, 0, sorted, 0, nums.length);//deep clone数组
Arrays.sort(sorted);
int left = 0, right = sorted.length - 1;//新数组里面目标的两个数的indices
while (left < right) {
if (sorted[left] + sorted[right] < target) {
left++;
} else if (sorted[left] + sorted[right] > target) {
right--;
} else {//找到新数组里面的两个数了
break;
}
}
int index1 = -1, index2 = -1; //初始值为-1，不为0，这样知道两个indices是否找到原来数组的对应两个数的索引从而改变过
for (int i = 0; i < nums.length; i++) {
if (nums[i] == sorted[left] || nums[i] == sorted[right]) {//只可能一个解
if (index1 == -1) {
index1 = i;
} else {
index2 = i;
}
}
}
int [] result = {index1, index2};
Arrays.sort(result);//之前不知道index1和index2哪个在前，所以需要sort一下
return result;
}
}