本文由作者三汪首发于简书。
历史解题记录已同步更新github.
题目
Problem Description
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
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题目分析
题意是让我们返回给定数组中和为目标值的两个元素的下标。同时限定每个输入都将只有一个解，并且每个元素我们只能使用一次。
代码和思路
A.原始版本
看到这个题目。作为小白的我当然是不假思索地用了穷举法。时间复杂度O(n^2)。
好在这种粗暴的解决方案没有像后来看到的别人说的那样因为时间复杂度太高而被leetCode拒收，
还胜过了30.2%的Java Solution。
我认为原因大概是因为我用了个小聪明让内部循环的j=i+1而不是j=0。时
间复杂度虽然没变，但是实际上还是要更好一点的。
（如果你跟我一样是小白，深思熟虑后还是不理解为什么这样做，给我留言呀。我来告诉你~）
1.0版本代码如下：
/**
*
* <p>
* Description:我自己的第一个解决方案<br />
* 耗时：39ms
* </p>
* @author wugy
* @version 0.1 2017年12月4日
* @param nums
* @param target
* @return
* int[]
*/
private int[] twoSum_1_0(int[] nums, int target) {
int[] indices =new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[i]+nums[j]==target) {
indices[0]=i;
indices[1]=j;
return indices;
}
}
}
return null;
}
B.改进版本
有思考才有进步嘛。
我点进了leetCode上提供的用时最少（3ms）的solution研究了一下，又综合了网上一些朋友的心得。
(研究这道题断断续续的，时间跨度比较久。因此无法给出参考链接。只能在心里感谢一下这些朋友了)
我认为对这个问题最好的解决方式是使用Map来储存key-value。
key是nums[]的元素，value是nums[]对应元素的下标。
从代码量和时间复杂度来说，这种解决思路应该是最优雅的。
代码如下：
/**
*
* <p>
* Description:研究过别人代码以后的第二个改进版本<br />
* 耗时：9ms
* </p>
* @author wugy
* @version 1.1 2017年12月6日
* @param nums
* @param target
* @return
* int[]
*/
private int[] twoSum_1_2(int[] nums, int target){
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = target-nums[i];
if (map.containsKey(diff)) {
return new int[]{map.get(diff),i};
}
map.put(nums[i], i);
}
return null;
}
其实说实话我不知道为什么这个1.2版本的改进方案在leetCode上只能跑出9ms的成绩。
因为我看到7ms的Sample Solution和我这个版本的改进实际上是基本相同的。
leetCode告诉我我的这个版本打败了59.65%的Java Solution。
至于其他用时比较少的Solution，我觉得就比较扯了。
下面让我来告诉你扯在哪里。
C.LeetCode上用时最少的Java Solution
直接来分析这个用时3ms的solution吧
/**
*
* <p>
* Description:截至此刻leetCode上的最优解<br />
* 耗时：3ms<br />
* </p>
* 已发现2个无法通过的TestCase:<br />
* 1.Input:[2222222,2222222],4444444;Output:[0,1]<br />
* 2.Input:[-9,4,9,90],0;Output:[0,2]<br />
* @deprecated
* @version 0.1 2017年12月4日
* @param nums
* @param target
* @return
* int[]
*/
private int[] bestTwoSum(int[] nums, int target) {
int[] map = new int[20050];//完全无法理解为什么数组长度为20050。这种做法如果传入的数组中有比20050更大的值就挂了。已向leetCode提交TestCase
int size = 4;
for (int i = 0; i < nums.length; i++) {
map[nums[i] + size] = (i + 1);
int diff = target - nums[i + 1] + size;
if (diff < 0) continue;
int d = map[diff];
if (d > 0)
return new int[]{d - 1, i + 1};
}
return null;
}
拿到这个solution的时候我是懵逼的。
因为不知道为什么map[]数组定义成了20050的大小，也不知道为什么要定义一个size=4。
结合自己的理解对这种进行了重写以后。我慢慢地理解了这个solution。
因为这个solution纯属扯淡。
数组定义成20050的大小应该是因为已有TestCase中nums[]元素没有大于20050的。
size=4是因为TestCase中元素为负的的值最小为-3或-4。
有了size,后面代码中if (diff < 0) continue;的这个判断才有意义。也因此进一步减少了耗时。
在上面代码注释中，我给出了2个无法通过的TestCase。均已提交LeetCode。
思考
其实。如果能使用int[]数组来转换元素值与下标，实际上是更友好的。
而我们不这么做呢。因为int[]数组无法定义到足够存放-2147483648到2147483647的所有int数值，会OutOfMemory。
因此只能使用HashMap来代替它。
以上。
希望我的文章对你能有所帮助。
我不能保证文中所有说法的百分百正确，
但我能保证它们都是我的理解和感悟以及拒绝直接复制黏贴（确实需要引用的部分我会附上源地址）。
有什么意见、见解或疑惑，欢迎留言讨论。
