难度简单 2026-06-09 哈希表数组一次遍历

两数之和：用哈希表把查找压到一次遍历

摘要：这道题要求在数组中找到两个数，使它们的和等于目标值，并返回这两个数的下标。最直接的双重循环很好想，但时间复杂度是 O(n²)。更好的思路是边遍历边记录已经见过的数，把“找另一个数”变成哈希表里的 O(1) 查询。读完这题，你会掌握一类常见套路：当目标由两个元素共同决定时，先固定一个，再反查另一个。

一、题意转述

给定一个整数数组 nums 和一个目标值 target，需要找出两个不同位置的元素，让它们相加等于 target，并返回这两个位置的下标。

这题的关键条件有三个：

答案保证存在，并且只有一组有效答案。
同一个数组元素不能重复使用。
数组里可能有重复数字，也可能出现负数。

二、关键观察

如果当前遍历到的数是 x，那么它需要的另一个数一定是：

target - x

也就是说，我们不需要每次都去后面重新找一遍所有元素。只要维护一个“已经遍历过的数字 -> 下标”的映射，就可以在看到 x 时立刻问：

前面有没有出现过 target - x？

如果出现过，那么当前下标和那个下标就是答案。

三、解题思路

最朴素的做法是枚举两个下标 i 和 j，检查 nums[i] + nums[j] == target。这个方法的逻辑很直观，但会重复做大量查找。

更好的做法是使用哈希表：

创建一个字典 seen，记录已经遍历过的数字及其下标。
从左到右遍历数组。
对当前数字 nums[i]，计算它需要的补数 need = target - nums[i]。
如果 need 已经在字典里，直接返回 [seen[need], i]。
如果还没找到，就把当前数字和下标放入字典。

这里有一个很重要的顺序：先查，再存。

如果先把当前数字存进去，再去查补数，当 target = nums[i] * 2 时，就可能把同一个元素当成两个元素使用。先查再存，就能保证字典里只保存“当前元素之前”的位置。

四、算法推导

我们要找的是：

nums[a] + nums[b] = target

把式子移项：

nums[a] = target - nums[b]

当遍历到位置 b 时，nums[b] 已经固定，问题就从“找一对数”变成了：

之前有没有出现过 target - nums[b]？

哈希表刚好擅长回答“某个值是否出现过”这个问题。于是算法从双重循环变成一次遍历：

遍历 nums[i]
  计算 need = target - nums[i]
  如果 need 在 seen 中：返回 seen[need], i
  否则记录 nums[i] 的下标

这就是这题最核心的转换：把配对问题转成补数查找问题。

五、C# 实现

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        var seen = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++)
        {
            int need = target - nums[i];

            // 先查补数，确保不会重复使用当前元素
            if (seen.TryGetValue(need, out int index))
            {
                return new[] { index, i };
            }

            // 记录当前数字最后一次出现的位置即可
            seen[nums[i]] = i;
        }

        return Array.Empty<int>();
    }
}

这段代码里有两个 C# 细节值得注意：

Dictionary<int, int> 的 key 是数组里的数字，value 是下标。
用 TryGetValue 可以一次完成“是否存在 + 取出下标”，比先 ContainsKey 再索引访问更顺。

最后的 return Array.Empty<int>() 理论上不会走到，因为题目保证答案存在。保留它只是为了让方法在语法和工程习惯上完整。

六、复杂度分析

时间复杂度：O(n)。

每个元素最多遍历一次，每次哈希表查询和插入的平均复杂度都是 O(1)。

空间复杂度：O(n)。

最坏情况下，答案在数组靠后的位置，哈希表需要保存接近整个数组的元素。

七、易错点

第一，不能重复使用同一个元素。

这就是为什么代码要先查 need，再存 nums[i]。如果顺序反了，在某些写法里很容易把当前下标和自己配对。

第二，要处理重复数字。

例如两个相同的数相加刚好等于目标值时，不能只看数字是否相同，而要看下标是否不同。一次遍历的“先查再存”天然保证了这一点。

第三，不要只返回数字本身。

题目要的是下标，不是两个值。所以字典里必须存“数字 -> 下标”，而不是只存一个集合。

第四，不要被负数干扰。

负数不会改变算法。need = target - nums[i] 仍然成立，哈希表也可以正常存负数 key。

八、同类经典题

8.1 两数之和 II：输入有序数组

相似点：目标仍然是找两个数，使它们相加等于 target。

变化点：数组已经有序，而且通常要求使用更少额外空间。

迁移方式：有序数组可以不用哈希表，改用双指针。左指针指向小数，右指针指向大数；和小了就左指针右移，和大了就右指针左移。它和本题本质上都在减少查找范围，只是本题靠哈希表，有序版本靠单调性。

using System;

public class Solution
{
    public int[] TwoSum(int[] numbers, int target)
    {
        int left = 0;
        int right = numbers.Length - 1;

        while (left < right)
        {
            int sum = numbers[left] + numbers[right];

            if (sum == target)
            {
                // 这类题通常要求返回从 1 开始的下标
                return new[] { left + 1, right + 1 };
            }

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

        return Array.Empty<int>();
    }
}

复杂度：时间复杂度 O(n)，空间复杂度 O(1)。

8.2 三数之和

相似点：仍然是在找若干个数，使它们的和满足目标条件。

变化点：从两个数变成三个数，而且要处理重复答案。

迁移方式：可以先固定一个数，把剩下的问题变成“两数之和”。不过因为三数之和通常要求返回不重复的三元组，所以更常见的做法是排序后固定一个数，再用双指针找另外两个数。

using System;
using System.Collections.Generic;

public class Solution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        Array.Sort(nums);
        var answer = new List<IList<int>>();

        for (int i = 0; i < nums.Length - 2; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }

            int left = i + 1;
            int right = nums.Length - 1;

            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0)
                {
                    answer.Add(new List<int> { nums[i], nums[left], nums[right] });

                    int leftValue = nums[left];
                    int rightValue = nums[right];

                    while (left < right && nums[left] == leftValue)
                    {
                        left++;
                    }

                    while (left < right && nums[right] == rightValue)
                    {
                        right--;
                    }
                }
                else if (sum < 0)
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
        }

        return answer;
    }
}

复杂度：时间复杂度 O(n²)，空间复杂度 O(1)，不计返回结果占用的空间。

8.3 四数之和

相似点：继续沿用“固定一部分，再寻找剩余部分”的思路。

变化点：枚举层数更多，重复组合更多，剪枝更重要。

迁移方式：可以固定前两个数，把问题降成“两数之和”的变体。和三数之和一样，排序、去重和剪枝会成为重点。当前题里的“把目标拆成补数”仍然是底层思想，只是外面多了几层约束。

using System;
using System.Collections.Generic;

public class Solution
{
    public IList<IList<int>> FourSum(int[] nums, int target)
    {
        Array.Sort(nums);
        var answer = new List<IList<int>>();

        for (int first = 0; first < nums.Length - 3; first++)
        {
            if (first > 0 && nums[first] == nums[first - 1])
            {
                continue;
            }

            for (int second = first + 1; second < nums.Length - 2; second++)
            {
                if (second > first + 1 && nums[second] == nums[second - 1])
                {
                    continue;
                }

                int left = second + 1;
                int right = nums.Length - 1;

                while (left < right)
                {
                    long sum = (long)nums[first] + nums[second] + nums[left] + nums[right];

                    if (sum == target)
                    {
                        answer.Add(new List<int>
                        {
                            nums[first],
                            nums[second],
                            nums[left],
                            nums[right]
                        });

                        int leftValue = nums[left];
                        int rightValue = nums[right];

                        while (left < right && nums[left] == leftValue)
                        {
                            left++;
                        }

                        while (left < right && nums[right] == rightValue)
                        {
                            right--;
                        }
                    }
                    else if (sum < target)
                    {
                        left++;
                    }
                    else
                    {
                        right--;
                    }
                }
            }
        }

        return answer;
    }
}

复杂度：时间复杂度 O(n³)，空间复杂度 O(1)，不计返回结果占用的空间。这里用 long 计算四数之和，是为了避免多个较大整数相加时发生 int 溢出。

九、复盘总结

两数之和是一道非常适合建立“哈希表查找感”的题。

它的关键不是记住代码，而是记住这个转换：

找 a + b = target
=> 固定 b，查 a = target - b

当你以后遇到“找两个元素满足某种关系”的题，可以先问自己两个问题：

如果固定当前元素，另一个元素能不能被算出来？
这个“另一个元素”能不能用哈希表快速查到？

只要这两个问题的答案都是肯定的，就很可能能把 O(n²) 的枚举优化成 O(n) 的查找。