• 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;
  }
  

  结果：出现了两个问题
  • 
  1. 使用快排后堆栈溢出。
  2. 当nums为负数的时候，无法得到其中转折处数字。

3. 使用哈希列表

• 首先将所有元素和index放入hashmap中，然后循环数组，每次去找target-nums[i]是否在hashmap中。找到后返回i和hashmap中的index。

  public 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");
  }
  

  Runtime：10 ms
  Beats：56.03%
  时间复杂度：O(n)
  空间复杂度：O(n)
  将此算法优化，将两个循环归为一个循环，并且不做i的判断。

  public 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");
  }
  

  Runtime：8 ms
  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。
  以最大的数字为下标去申请数组空间。

  public 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;
  }
  

  Runtime：3ms

6.总结

• 两数运算得一数时。
  1. 冒泡 初级并且低效。
  2. 哈希表。
  3. 排序后首尾缩小得到两数。
  4. 知道最大数，使用数组下标最快。