1. Two Sum

Problem

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].

给定一个整数数组，当两个数相加等于目标值时，返回其下表。
你可以假设每一组输入都仅有一个确切的结果，你不可以使用同样的元素两次。

Solution

Brute Force/暴力破解

遍历每一个元素x，并且寻找另一个元素y，使得y = target - x。

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

复杂度分析

• 时间复杂度：O(n​²)
  对于每个元素，我们试图通过遍历数组中的其他元素O(n²)来找到匹配的结果。因此，时间复杂度是O(n​²)。
• 空间复杂度：O(1)

Tow-pass Hash Table/二次遍历散列表

为了改进时间复杂度，我们需要一种更有效的方式来检查数组中是否存在对应的元素。如果对应元素存在，我们需要查询它的下标。我们可以通过Hash表来存储每一个元素的下标。
我们使用hash表来将查询的时间复杂度从O(n)降到O(1)。hash表的查询时间近似于一个常量，但是当碰撞发生时，一次查询可能需要O(n)的时间。当hash方法选择得当时，一次查询的时间仅需要O(1)。
一个简单的实现就是使用二次遍历。在第一次遍历时，我们将每一个元素的值和下标添加到hash表中。然后，在第二次遍历时，我们查询每个元素的对应值是否存在(target - nums[i])。注意对应值不能是nums[i]自身。

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

复杂度分析

• 时间复杂度：O(n)。我们遍历了包含n个元素的列表两次。通过hash表将查询时间下降到O(1)，因此时间复杂度是O(n)。
• 空间复杂度：O(n)。存储n个元素的hash表使用了额外的存储空间，因此空间复杂度是O(n)。

One-pass Hash Table/一次遍历散列表

我们可以使用一次遍历来实现。当我们遍历并且插入元素的时候，我们同时回看并且复查是否有对应的元素已经存在于散列表中。如果存在我们就得到了一个解，并且立刻返回结果。

public int[] twoSum(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 };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析

• 时间复杂度：O(n)。我们遍历了包含n个元素的列表一次。每次查询耗时O(1)。
• 空间复杂度：O(n)。存储n个元素的hash表使用了额外的存储空间。