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].简单来说，就是给一个数组及一个数值，求数组中两元素相加为该数值对应的两个索引。且要求index1小于index2，而且答案结果稳定。
public class Solution { public int[] twoSum(int[] nums, int target) { int[] numsUnOrder = new int[nums.length]; for (int i = 0; i < nums.length; i++) {//原始无序数组,不能直接使用int[] numsUnOrder = nums;这样是引用传递，指向的还是nums[] numsUnOrder[i] = nums[i]; } int[] result = new int[2]; Arrays.sort(nums);//对数组做了一次排序，默认升序排列 int begin = 0; int end = nums.length - 1; int temp; while (begin < end) { if (nums[begin] + nums[end] == target) { result[0] = nums[begin];//先存放数值 result[1] = nums[end]; break; } else if (nums[begin] + nums[end] < target) { begin++; } else if (nums[begin] + nums[end] > target) { end--; } }//while for (int i = 0; i < numsUnOrder.length; i++) {//从前往后比较，根据数值在原始无序数组中查询下标，并把下标存到result[]中 if (result[0] == numsUnOrder[i]) { result[0] = i; break; } } //可能会出现两个相同的元素，所以需要一个从前往后查找下标，一个从后往前查找下标 for (int i = numsUnOrder.length - 1; i >= 0; i--) {//从后往前比较，根据数值在原始无序数组中查询下标，并把下标存到result[]中 if (result[1] == numsUnOrder[i]) { result[1] = i; break; } } if (result[0] > result[1]) {//保证result[0]比result[1]小 temp = result[0]; result[0] = result[1]; result[1] = temp; } return result; }//twoSum }
19 / 19 test cases passed. Status: Accepted Runtime: 7 ms Your runtime beats 92.64 % of java submissions
-------------------------------------------------------
//AC 方法2 public int[] twoSum(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 result; }19 / 19 test cases passed. Status: Accepted Runtime: 38 ms Your runtime beats 29.73 % of java submissions.
时间复杂度是O(n^2),
------------------------------------------------------
其他更好的方法：
/** * 2020-11-25 * * @param nums * @param target * @return */ public int[] twoSum2(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 complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[]{i, map.get(complement)};//res[0]比res[1]小 } } throw new IllegalArgumentException("No two sum solution"); } /** * 2020-11-25 * @param nums * @param target * @return */ public int[] twoSum3(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i };//res[0]比res[1]小 } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } /** * 与twoSum3同义 * 后面的每一个元素与之前元素组成的map比较，如果差值正在好map中，则返回；反之把当前值及下标放入map中，继续遍历下一个元素 * @param nums * @param target * @return */ int[] twoSum5(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int sub = target - nums[i]; if (map.containsKey(sub)) { return new int[]{map.get(sub), i};//map.get(sub)是前面值的下标，所以比i小，i是后面值的下标 } map.put(nums[i], i); } throw new IllegalArgumentException("no answers!"); } public static void main(String[] args) { Solution_1_TwoSum solution_1_twoSum = new Solution_1_TwoSum(); int[] res = solution_1_twoSum.twoSum3(new int[]{1, 3, 4, 3}, 8); System.out.println(res[0] + "," + res[1]); //Exception in thread "main" java.lang.IllegalArgumentException: No two sum solution int[] res = solution_1_twoSum.twoSum3(new int[]{1, 3, 4, 3}, 7); System.out.println(res[0] + "," + res[1]);//1,2 int[] res4 = solution_1_twoSum.twoSum2(new int[]{1, 3, 4, 3}, 7); System.out.println(res4[0] + "," + res4[1]);//1,2 int[] res3 = solution_1_twoSum.twoSum2(new int[]{1, 3, 3, 4}, 7); System.out.println(res3[0] + "," + res3[1]);//1,3 int[] res2 = solution_1_twoSum.twoSum2(new int[]{1, 3, 3, 4}, 6); System.out.println(res2[0] + "," + res2[1]);//1,2 }
