- 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.可能會(huì)有兩個(gè)相同的數(shù)字。
2.注意有負(fù)數(shù)。
1.最容易想到的解法
- 冒泡查詢到目標(biāo)數(shù)字，找出位數(shù)，返回即可。
代碼如下：
運(yùn)行結(jié)果：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%
時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)
2. 第二種進(jìn)階方法
- 先快速排序數(shù)組，然后將i和i+1相加，取剛好大于target的兩數(shù)，然后進(jìn)行兩個(gè)循環(huán)，小數(shù)和其后的所有數(shù)進(jìn)行相加尋找target-小數(shù)，大數(shù)和其前的所有數(shù)進(jìn)行相加尋找target-大數(shù)。
結(jié)果：出現(xiàn)了兩個(gè)問(wèn)題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; }- 使用快排后堆棧溢出。
- 當(dāng)nums為負(fù)數(shù)的時(shí)候，無(wú)法得到其中轉(zhuǎn)折處數(shù)字。
3. 使用哈希列表
- 首先將所有元素和index放入hashmap中，然后循環(huán)數(shù)組，每次去找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%
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
將此算法優(yōu)化，將兩個(gè)循環(huán)歸為一個(gè)循環(huá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%
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
4. 2方法的進(jìn)階優(yōu)化
-
使用arrays.sort方法進(jìn)行快排，然后首位之和大于target則尾部index減1，小于target則首位index加1。這樣找到和剛好與target相等的數(shù)字，循環(huán)后找到index數(shù)組。
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%針對(duì)該方法再次進(jìn)行優(yōu)化
首先復(fù)制數(shù)組使用Arrays.copyOf()
將兩次循環(huán)摘出來(lái)一個(gè)函數(shù)。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. 最快的方法
- 投機(jī)取巧，首先，知道數(shù)列中最大的數(shù)字。20050
知道數(shù)列中最大的負(fù)數(shù)。size=5。
以最大的數(shù)字為下標(biāo)去申請(qǐng)數(shù)組空間。
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.總結(jié)
- 兩數(shù)運(yùn)算得一數(shù)時(shí)。
- 冒泡 初級(jí)并且低效。
- 哈希表。
- 排序后首尾縮小得到兩數(shù)。
- 知道最大數(shù)，使用數(shù)組下標(biāo)最快。
