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

Test Case

Given	When	Then
nums = [2, 7, 11, 15], target = 9	Calculate indices of the two numbers	return [2, 7]
nums = [1, 2, 3, 4], target = 7	Calculate indices of the two numbers	return [3,4]
nums = [2, 8, 11, 15], target = 9	Calculate indices of the two numbers	return []

Solution

Exhaustion

通过穷举的方法寻找两数和为target的目标元素

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[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

复杂度分析

• 时间复杂度: O(n²)

  对于每个元素，我们通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n²)。

• 空间复杂度: O(1)

Hash

使用哈希表以空间换时间的方式, 将O(n)的时间复杂度降到O(1), 但空间复杂度提高到O(n)

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int expectedNumber = target - nums[i];
            if (map.containsKey(expectedNumber)) {
                return new int[]{map.get(expectedNumber), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

复杂度分析

• 时间复杂度: O(n)

  哈希表将查找时间缩短到O(1), 我们需要把所有元素遍历一次, 所以时间复杂度为O(n)

• 空间复杂度: O(n)

  所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。