Leetcode刷题记录-01：two-sum

为了锻炼英语能力 + 算法能力咱选择在海外版的 Leetcode 进行练习，下面咱们先来看看题目描述。

Description

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.

Example 1:

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

1
2
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

解法

最简单的解法是遍历 nums 数组，把不同下标的两个数进行相加并检查其结果是否与 target相等，其时间复杂度为 O(n^2) ，空间复杂度为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int arr_size = nums.size();

        /* brute-force */
        for (int i = 0; i < arr_size; i++) {
            for (int j = i + 1; j < arr_size; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }

        /* not found */
        return {};
    }
};

虽然说这样的代码可以通过检查，但如此之高的空间复杂度并非是我们所想要的（悲），比较通用的优化思路是使用空间换时间的方法。

注意到我们所想要的是一组 {nums[i], nums[j]}，其同时满足 i != j a与 nums[i] + nums[j] == target，因此我们可以在遍历过程中记录每个 nums[i] 并计算 target - nums[record] 以观测其是否与我们所经过的每个 nums[i] 相等，而这仅需要 O(N) 的时间复杂度与 O(N) 的空间复杂度。

这个记录结构很像 哈希表 ，由此优化后的我们最终的代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <unordered_map>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        int arr_size = nums.size();

        /* use map to optimize */
        for (int i = 0; i < arr_size; i++) {
            if (map.find(target - nums[i]) == map.end()) {
                map[nums[i]] = i;
            } else {
                return {map[target - nums[i]], i};
            }
        }

        /* not found */
        return {};
    }
};