[LeetCode] 1. Two Sum

发表于 Disqus：

LeetCode 1. Two Sum (两数之和) Diffculty: Eazy

Question

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.

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

Example

Example 1

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Example 2

1
2
[3, 2, 3]
6

Solution

题意分析

  • Input：一个整数数组 nums；一个目标值 target
  • Output：数组中两个元素之和等于目标值的两个元素的下标组成的一个长度为 2 的整数数组
  • 即是需要从 nums 中依次遍历，计算并判断 n 和 n + 1 的和（nums[n] + nums[n + 1] == target），然后将 n 和 n + 1 作为数组输出结果（[n, n + 1]）
  • n 的范围是 [0, nums.length)

Java

My Solution 1

解题思路

用两个循环分别遍历数组索引为 n 和 n + 1 的元素，并判断两个元素之和是否与目标值相同。

解题步骤
  1. 循环 1，范围：[0, nums.length)，获取 n 的元素
  2. 循环 2，嵌套在循环 1 中，范围：[1, nums.length)，获取 n + 1 的元素
  3. 循环 2 中，判断 nums[n] + nums[n + 1] == target，如为 true，则 return new int[] {n, n + 1}
Code
初版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] twoSum(int[] nums, int target) {
    int[] results = new int[2];

    int length = nums.length;
    for (int i = 0; i < length; i++) {
        for (int j = i; j < length; j++) {
            if (j > i) {
                int a = nums[i];
                int b = nums[j];

                int sum = a + b;
                if (sum == target) {
                    results[0] = i;
                    results[1] = j;
                }
            }
        }
    }

    return results;
}
优化版
1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            if (j > i && nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }

    throw new IllegalArgumentException("No two sum solution");
}
总结

这种解题思路实际就与 LeetCode 提供的 Solution 1 一样。

LeetCode Solution 1: Brute Force

The brute force approach is simple. Loop through each element xx and find if there is another value that equals to target - x.

暴力法很简单。遍历每个元素 x，并查找是否存在一个值与 target - x 相等的目标元素。

Code
1
2
3
4
5
6
7
8
9
10
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");
}
Complexity Analysis
  • 时间复杂度：$O(n^2)$，对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 $O(n)$ 的时间。因此时间复杂度为 $O(n^2)$。
  • 空间复杂度：$O(1)$。

LeetCode Solution 2: Two-pass Hash Table

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

We reduce the look up time from $O(n)$ to $O(1)$ by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say “near” because if a collision occurred, a look up could degenerate to $O(n)$ time. But look up in hash table should be amortized $O(1)$ time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. In the first iteration, we add each element’s value and its index to the table. Then, in the second iteration we check if each element’s complement (target - nums[i]) exists in the table. Beware that the complement must not be nums[i] itself!

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 $O(n)$ 降低到 $O(1)$。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 $O(n)$。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 $O(1)$。

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i] 本身！

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
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");
}
Complexity Analysis
  • 时间复杂度：$O(n)$，我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 $O(1)$ ，所以时间复杂度为 $O(n)$。
  • 空间复杂度：$O(n)$，所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。

LeetCode Solution 3: One-pass Hash Table

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

Code
1
2
3
4
5
6
7
8
9
10
11
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");
}
Complexity Analysis
  • 时间复杂度：$O(n)$，我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 $O(1)$ 的时间。
  • 空间复杂度：$O(n)$，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

Summary

因为 LeetCode 提供的 Solution 是依次的基于不同情况下的实现和优化，是逐步递进的，所以我把这三个 Solution 也一起贴过来了。

解决这个问题运用到了 数组（Array）和 哈希表（Hash Table）两种数据结构。在实际开发中，需要基于不同的情况来使用，比如数据量级小或快速开发，那当然就使用暴力法，怎么简单怎么来。但当涉及到性能时，就要综合考虑选择了。

References