问题：
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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
官方难度：
Easy
翻译：
给定一个整型数组和一个给定值，返回数组中两数的下标，这两数的和为给定值，假设解集唯一确定。
例子：
给定数组{2,7,11,15}，给定值9，返回下标[0,1]。
方法一：
- 利用一个二次循环，在之后的数组中查找target-nums[i]是否存在。
方法一的解题代码：
public static int[] method_1(int[] nums, int target) {
for (int i = 0; i < nums.length - 1; i++) {
int numberToFind = target - nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == numberToFind) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
method_1
方法二：
- 相对而言，在Java里面，数组是一种帮助方法相对较少的数据结构，我们可以期盼，有一种方法，可以快速的定位是否存在某一个给定的值，那么相对就可以减少内循环的时间开销。
- 第一个想法是List集合，List集合有List.contains()方法，迅速定位List集合中是否存在某一给定的元素，同时数组的帮助方法Arrays.asList()，可以直接将数组转化为List集合。同时，还有List.indexOf()方法，来定位下标。
- 想法总是美好的，但是这一方法的雷区实在太多。
- 数组和集合有一个很重要的差别在于，集合不能接收基本类型，你可能会想象Arrays.asList()能触发自动装箱，但是很可惜，int[]也是List集合能够接收的类型。所以你需要先显式地将int[]转化为Integer[]。
- List.indexOf(target)是获取集合中第一个为target的下标，那么就无法定位例如nums[]={2,1,2}，target=4的问题。这时候自然地会想到利用List.lastIndexOf()方法。但是问题又来了，例如nums[]={3,2,4},target=6的问题，返回的数组为[0,0]，所以要优先加上index1!=idnex2的判断条件。
- 鉴于有这么多的雷区，就时间消耗上看，也不见得有多少提升，可能还比方法一有所不如，不推荐使用这种方法。
方法二的解题代码：
public static int[] method_2(int[] nums, int target) {
// 先将int[]转成Integer[]
Integer[] collectionArray = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
collectionArray[i] = nums[i];
}
List<Integer> list = new ArrayList<>();
list = Arrays.asList(collectionArray);
for (Integer a : list) {
if (list.contains(target - a)) {
// 防止原数组有重复数字的情况
int index1 = list.indexOf(a);
int index2 = list.lastIndexOf(target - a);
if (index1 != index2) {
return new int[] { index1, index2 };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
method_2
方法三：
- 无论是方法一，还是方法二的算法，最大的缺点在于，它需要在剩余数组中寻找结果，当数组很大的时候，这种时间开销就相当庞大了。其实我们可以将已经遍历过的数字放入另一个数据结构中，在这个数据结构中寻找解集。
方法三的解题代码：
public static int[] method_3(int[] nums, int target) {
List<Integer> list = new ArrayList<>();
list.add(nums[0]);
for (int i = 1; i < nums.length; i++) {
if (list.contains(target - nums[i])) {
return new int[] { list.indexOf(target - nums[i]), i };
}
list.add(nums[i]);
}
throw new IllegalArgumentException("No two sum solution");
}
method_3
方法四：
- 仔细分析方法三中算法的时间开销，不难发现List.contains()方法在List集合中查找的效率决定了整个算法的时间开销。那么List.contains()是不是最优的查找方式呢？
- 说到查找速度，不可避免地想到了哈希表，自然而然的，就考虑尝试使用HashMap的数据结构，将nums[i]作为key，i作为value，同时Map集合提供Map.containsKey()方法在HashMap的实现上，拥有更高的效率。
方法四的解题代码：
public static int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length < 2) {
throw new IllegalArgumentException("Input error");
}
Map<Integer, Integer> map = new HashMap<>();
map.put(nums[0], 0);
for (int i = 1; i < nums.length; i++) {
int numberToFind = target - nums[i];
if (map.containsKey(numberToFind)) {
return new int[] { map.get(numberToFind), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
twoSum
备注：
- 一般的算法，需要考虑入参的合理性，这一点在方法四的代码中有写出。
- 可以将第一个元素直接放入集合，循环从i=1开始，可以省去一次判断的操作。
- 虽然哈希表拥有很高的速度，但是Map的空间的开销要远比List来得多，如果效率提升不大的话，尽可能还是不要用Map了。当然，本题中对于时间效率的提升还是值得的。
相关链接：
https://leetcode.com/problems/two-sum/
PS：如有不正确或提高效率的方法，欢迎留言，谢谢！