0%

两数之和

发表于 更新于 分类于

1. 两数之和 [简单]

题目说明

Leetcode题目链接

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解题思路

暴力枚举

  • 时间复杂度：O(n^2)

  • 空间复杂度：O(1)

哈希

遍历整个数组，通过 Hashmap 查看 target-nums[i] 是否存在，若不存在则将 (nums[i], i)加入到 Hashmap 中。

  • 时间复杂度：O(n)

  • 空间复杂度：O(n)

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

        for (int i = 0; i < nums.size(); i++)
        {
            int looking = target - nums[i];
            if (hash_map.find(looking) != hash_map.end())
            {
               return {i, hash_map.at(looking)}; 
            }

          	// add current num into map
            hash_map[nums[i]] = i;
        }

        return {};
    }
};

排序+双指针

将数组排序后，使用双指针 left right 分别指向数组的头和尾，比较两数之和与 target 的大小，向中间逼近。

  • 时间复杂度：O(nlogn)

  • 空间复杂度：O(n) (若题目要求返回数值则为O(1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> vec_num_index;
        for (int i = 0; i < nums.size(); i++)
        {
            vec_num_index.push_back(pair(nums[i], i));
        }
        sort(vec_num_index.begin(), vec_num_index.end());

        int left = 0;
        int right = vec_num_index.size() - 1;
        while (left < right)
        {
            auto left_num = vec_num_index[left].first;
            auto right_num = vec_num_index[right].first;
            auto sum = left_num + right_num;
            if (sum == target)
            {
                return {vec_num_index[left].second, vec_num_index[right].second};
            }

            if (sum < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }

        return {};
    }
};

思路对比

  1. 如果要求返回数值，哈希更快但需要O(n)的内存消耗，双指针需要排序的耗时但不需要额外空间。
  2. 如果要求返回下标，双指针算法需要建立带下标的 pair 数组，也需要O(n)的内存消耗，则哈希更优。
  3. 如果输入有序数组，则双指针更优。