- Two Sum 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]. - Tips：
1.可能会有两个相同的数字。
2.注意有负数。
1.最容易想到的解法
- 冒泡查询到目标数字，找出位数，返回即可。
代码如下：
运行结果：public int[] twoSumOne(int[] nums, int target) { int[] result = 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) { result[0] = i; result[1] = j; return result; } } } return null; }
Runtime: 39 ms
Beats: 30.80%
时间复杂度：O(n^2)
空间复杂度：O(1)
2. 第二种进阶方法
- 先快速排序数组，然后将i和i+1相加，取刚好大于target的两数，然后进行两个循环，小数和其后的所有数进行相加寻找target-小数，大数和其前的所有数进行相加寻找target-大数。
结果：出现了两个问题public int[] twoSumTwo(int[] nums, int target) { int[] result = new int[2]; ArrayList<Integer> numsSort = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { numsSort.add(nums[i]); } Arrays.sort(nums); int[] resultNum = new int[2]; int small = -1; int large = -1; for (int i = 0; i < nums.length - 1; i++) { if (nums[i] + nums[i + 1] == target) { resultNum[0] = nums[i]; resultNum[1] = nums[i + 1]; } else if (nums[i] + nums[i + 1] > target) { small = i; large = i + 1; } } if (small != -1 || large != -1) { for (int i = 0; i < large; i++) { if (nums[i] + nums[large] == target) { resultNum[0] = nums[i]; resultNum[1] = nums[large]; } } for (int i = nums.length - 1; i > small; i--) { if (nums[i] + nums[small] == target) { resultNum[0] = nums[small]; resultNum[1] = nums[i]; } } } for (int i = 0; i < numsSort.size(); i++) { if (numsSort.get(i) == resultNum[0] && result[0] == 0) { result[0] = i; } else if (numsSort.get(i) == resultNum[1] && result[1] == 0) { result[1] = i; } } return result; } public int[] quickSort(int[] array, int begin, int end) { if (array == null || begin < end) { int p = patition(array, begin, end); quickSort(array, begin, p - 1); quickSort(array, p + 1, end); } return array; } private int patition(int[] array, int begin, int end) { int key = array[begin]; while (begin < end) { while (begin < end && array[end] >= key) { end--; } array[begin] = array[end]; while (begin < end && array[begin] < key) { begin++; } array[end] = array[begin]; } array[begin] = key; return begin; }- 使用快排后堆栈溢出。
- 当nums为负数的时候，无法得到其中转折处数字。
3. 使用哈希列表
- 首先将所有元素和index放入hashmap中，然后循环数组，每次去找target-nums[i]是否在hashmap中。找到后返回i和hashmap中的index。
Runtime：10 mspublic int[] twoSumThree(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int other = target - nums[i]; if (map.containsKey(other) && map.get(other) != i) { return new int[]{i, map.get(other)}; } } throw new IllegalArgumentException("No two sum solution"); }
Beats：56.03%
时间复杂度：O(n)
空间复杂度：O(n)
将此算法优化，将两个循环归为一个循环，并且不做i的判断。
Runtime：8 mspublic int[] twoSumFour(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])) { return new int[]{i, map.get(target - nums[i])}; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); }
Beats：76.25%
时间复杂度：O(n)
空间复杂度：O(n)
4. 2方法的进阶优化
-
使用arrays.sort方法进行快排，然后首位之和大于target则尾部index减1，小于target则首位index加1。这样找到和刚好与target相等的数字，循环后找到index数组。
public int[] twoSumFive(int[] nums, int target) { int[] result = new int[2]; int[] copyNum = new int[nums.length]; for (int i = 0; i < copyNum.length; i++) { copyNum[i] = nums[i]; } Arrays.sort(copyNum); int left = 0; int right = copyNum.length - 1; while (left < right) { int sum = copyNum[left] + copyNum[right]; if (sum == target) { break; } else if (sum > target) { right--; } else { left++; } } for (int i = 0; i < nums.length; i++) { if (nums[i] == copyNum[left]) { result[0] = i; } } for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] == copyNum[right]) { result[1] = i; } } return result; }Runtime：6ms
Beats：98.91%针对该方法再次进行优化
首先复制数组使用Arrays.copyOf()
将两次循环摘出来一个函数。public int[] twoSumSix(int[] nums, int target) { int[] sortNums = Arrays.copyOf(nums, nums.length); Arrays.sort(sortNums); int i = 0; int j = sortNums.length - 1; while (i < j) { if (sortNums[i] + sortNums[j] == target) { return twoIndexes(sortNums[i], sortNums[j], nums); } else if (sortNums[i] + sortNums[j] > target) { j--; } else { i++; } } return new int[2]; } public int[] twoIndexes(int num1, int num2, int[] nums) { int[] res = new int[2]; int count = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == num1 || nums[i] == num2) { res[count] = i; count++; } } return res; }Runtime：5ms
5. 最快的方法
- 投机取巧，首先，知道数列中最大的数字。20050
知道数列中最大的负数。size=5。
以最大的数字为下标去申请数组空间。
Runtime：3mspublic int[] twoSumEight(int[] nums, int target) { int[] map = new int[20050]; int size = 5; 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; }
6.总结
- 两数运算得一数时。
- 冒泡 初级并且低效。
- 哈希表。
- 排序后首尾缩小得到两数。
- 知道最大数，使用数组下标最快。
