1. Two Sum 1️⃣

Array Hash Table

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice You can return the answer in any order.

问题：HashMap 的key值相同的话，value 会被覆盖, 当元素和它的目标值相同时，会影响结果吗？
答：不会，以两遍哈希表为例：检查当前元素的目标值时，是从前向后的，而覆盖的值一定在最后，不会出现目标值被覆盖的情况。以一遍哈希表为例：该方法在向map中插入元素时，会检查是否有该元素的目标元素，有的话就不会插入了。

暴力法

简单的暴力遍历，每次i选择一个元素，j从i之后一个元素遍历（因为每个元素只能使用一次，但是数组中元素可以重复！！！）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

两遍哈希表

我们需要检查数组中是否存在目标元素，若存在，还需要找到他的索引。保存数组中每个元素与其索引相互对应的最好办法是：哈希表

使用两次便利，第一次遍历将每个元素的值和它的索引添加到表中，第二次遍历，检查每一个元素的目标元素是否在表中。注意目标元素不能是nums[i]本身（因为每个元素只能使用一次，但是数组中元素可以重复！！！）

class Solution {
    public int[] twoSum(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 pair = target - nums[i];
            if (map.containsKey(pair) && map.get(pair) != i) {
                return new int[] {i, map.get(pair)};
            }
        }
        throw new IllegalArgumentException("No two num solution");
    }
}

一遍哈希表

在第一遍历将元素插入表中的同时，检查表中是否存在当前元素的目标元素，若存在则找到了目标解。
Q: 为什么只遍历一遍？为什么遍历时只查看该元素之前的集合就可以了呢？
A: 想想排列组合呀，你在数两两组合时，不也是这样操作的吗~

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int pair = target - nums[i];
            if (map.containsKey(pair)) {
                return new int[] {i, map.get(pair)};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two num solution");
    }
}