准备开始更新 LeetCode 题解，难一些的题目会尽可能给出直观的图像来讲解，简单的题解尽可能题解写的短一些，重点会加粗标记。 - 挖坑开始
应要求，代码会写 C++, Go 两个版本🎉，代码可能写的很烂，未来尽可能优化一下 逃~
每篇文章都会有标签，方便查询

两数之和

题目描述

给定一个整数数组 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]

哈希表 - $O(N)$

哈希表

题目要求解出满足 $x + y = target$ 的数对 $(x, y)$，对其变换得到 $x = target - y$

因此可以通过枚举 $x$ 的方式将问题转换成：找出数组中值为 $target - y$ 的元素的下标

由于题目保证：答案是唯一的，因此用哈希表直接记录每个元素的位置即可

时间复杂度 - $O(N)$

  • 枚举所有元素的复杂度是 $O(N)$
  • 哈希表插入和查询复杂度是 $O(1)$

代码

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    S := map[int]int{}
    for idx, val := range nums {
        if pos, ok := S[target - val]; ok {
            return []int{pos, idx}
        }
        S[val] = idx
    }
    return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int > S;
        vector<int > res;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (S.count(target - nums[i])) {
                res.push_back(i), res.push_back(S[target - nums[i]]);
                break;
            }
            S[nums[i]] = i;
        }
        return res;
    }
};