LeetCode 1. 两数之和

1. 暴力枚举

这道题需要在数组中找到两个不同位置的元素，使它们的和等于给定的目标值 target，并返回这两个元素的索引。

最容易想到的方法就是暴力枚举。

使用两层 for 循环，依次检查数组中所有可能的数对。如果两个元素的和恰好等于 target，就返回它们对应的索引。

为了避免重复枚举，也为了保证不会使用同一个元素两次，内层循环可以直接从 i + 1 开始。

Python 代码：

Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    n=len(nums)
    for i in range(n):
        for j in range(i+1,n):
            if nums[i]+nums[j]==target:
                return [i,j]

C++ 代码：

C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return vector<int>{i, j};
            }
        }
    }
    return vector<int>();
}
};

这种方法理解起来很简单，但双层循环的时间复杂度为 O(n2)O(n^2)。

当数组长度增加时，需要检查的数对也会迅速增多。那么，有没有办法避免逐个枚举所有数对呢？

2. 哈希表优化

换个角度思考。

我们需要找到两个数 x 和 y，满足：

x+y=targetx+y=target

移项之后，可以得到：

y=target−xy=target-x

也就是说，当我们遍历到一个数 x 时，其实已经知道另一个数应该是多少了。

现在的问题就从“寻找两个数”，变成了“寻找一个确定的数”。

不过，如果每次都重新遍历数组寻找 y，仍然会产生大量重复查找。

这里可以使用哈希表来优化。

哈希表能够根据键快速查找对应的值，因此我们可以将已经遍历过的元素保存起来：

  • 键（Key）：元素的数值。
  • 值（Value）：元素在数组中的索引。

遍历数组时，先计算当前元素需要匹配的另一个数：

y = target - nums[i]

接着检查哈希表中是否已经存在 y。

如果存在，说明之前遍历过一个能够与当前元素组成目标值的数，直接返回两者的索引即可。

如果不存在，就把当前元素及其索引存入哈希表，继续遍历。

这样，每个元素只需要处理一次，不必反复扫描整个数组。

Python 代码：

Python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        hs=dict()
        for i in range(n):
            y=target-nums[i]
            if y in hs:
                return [i,hs[y]]
            hs[nums[i]]=i

C++ 代码：

C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hs;
        for (int i = 0; i < nums.size(); i++) {
            int y = target - nums[i];
            if (hs.count(y))
                return vector<int>{i, hs[y]};
            hs[nums[i]] = i;
        }
        return vector<int>{};
    }
};

这里有一个值得注意的细节：为什么要先查询哈希表，再将当前元素存进去？

因为题目要求使用两个不同位置的元素。如果先插入再查询，就有可能把当前元素与它自己匹配。

例如，数组为 [3, 3]，目标值为 6。

遍历第一个 3 时，哈希表中还没有需要的 3，于是将它和索引 0 存进去。

遍历第二个 3 时，就能找到之前保存的元素，返回两个不同的索引。

因此，先查询、后插入的顺序不能随意颠倒。

3. 复杂度分析

对比两种方法：

解法时间复杂度额外空间复杂度
暴力枚举O(n2)O(n^2)O(1)O(1)
哈希表平均 O(n)O(n)O(n)O(n)

暴力枚举不需要额外的数据结构，但最坏情况下需要检查 O(n2)O(n^2) 个数对。

哈希表则用额外的空间保存已经遍历过的元素。在哈希查询和插入平均为 O(1)O(1) 的情况下，只需遍历一次数组，整体时间复杂度就能降到 O(n)O(n)。

这道题的关键在于：利用 target - x 确定需要查找的数，再通过哈希表避免重复遍历。

相比直接枚举所有数对，这种方法用额外的存储空间换来了更高的平均查询效率。

谢谢你读到这里。 ✧

聊两句

评论审核后显示

有疑问、补充，或者想交流一下，都可以写在这里。

评论区将在滚动到这里时加载。