DSA Interview Prep · 课时

两数之和及其多种变体

Q: 「两数之和及其多种变体」课时是免费的吗？

是的 — 「两数之和及其多种变体」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

Q: 「两数之和及其多种变体」这节课中我会学到什么？

使用哈希映射和双指针解决两数之和、三数之和、四数之和及有序数组两数之和，并比较时间与空间成本。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

Q: 「两数之和及其多种变体」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

使用哈希映射和双指针解决两数之和、三数之和、四数之和及有序数组两数之和，并比较时间与空间成本。

第 2 / 4 课13 个步骤

两数之和及其多种变体 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

两数之和：经典面试问题

LeetCode 1《两数之和》：给定一个未排序的数组和一个目标值，返回两个相加等于目标值的元素的索引。O(n²) 的暴力方法会检查所有元素对。最优的 O(n) 方法使用哈希映射：对于每个元素 x，检查 target - x 是否已经存在于映射中。如果存在，则返回这两个元素的索引。如果不存在，则将 x 及其索引存入映射。

两数之和通常是面试中的第一个问题——熟练掌握它，表明您已经准备好解决更难的问题。

def twoSum(nums, target):
    seen = {}   # val -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []

print(twoSum([2, 7, 11, 15], 9))   # [0, 1]
print(twoSum([3, 2, 4], 6))        # [1, 2]
print(twoSum([3, 3], 6))           # [0, 1]

哈希映射为何适用于两数之和

哈希映射会存储目前为止已经遇到的每个元素。处理元素 x 时，如果映射中存在 target - x，那么这两个元素就构成一个有效的数对。关键是，始终先检查补数，再存储 x，这样可以避免将单个元素与自身配对的情况（例如，当 x == target/2 时，映射检查会在存储 x 之前进行，因此只有在存在两个副本时才会匹配）。

# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
    complement = target - x
    print(f'i={i} x={x} complement={complement} seen={seen}')
    if complement in seen:
        print(f'  Found: indices [{seen[complement]}, {i}]')
        break
    seen[x] = i

有序数组中的两数之和（双指针）

如果数组已经排序，并且您需要的是值的索引（而不是原始索引），请使用双指针技术：让左右指针从两端开始向中间移动。如果总和等于目标值，则返回结果。如果总和太小，则将左指针向右移动。如果总和太大，则将右指针向左移动。该方法的时间复杂度为 O(n)，空间复杂度为 O(1)——当数组已排序且内存受限时，它优于哈希映射方法。

def twoSumSorted(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]   # 1-indexed as per LeetCode 167
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return []

print(twoSumSorted([2, 7, 11, 15], 9))   # [1, 2]
print(twoSumSorted([2, 3, 4], 6))         # [1, 3]
print(twoSumSorted([-1, 0], -1))          # [1, 2]

三数之和（LeetCode 15）

LeetCode 15《三数之和》：找出所有和为零且不重复的三元组。对数组排序，逐个固定一个元素，然后在剩余的有序子数组上应用双指针。跳过重复值，以避免产生重复的三元组。时间复杂度为 O(n²)——这是该问题的最优复杂度，因为输出本身可能包含 O(n²) 个三元组。

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:  # skip duplicates
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s == 0:
                result.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                lo += 1; hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return result

print(threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0]))            # [[0,0,0]]

四数之和（LeetCode 18）

LeetCode 18《四数之和》：找出所有和为目标值且不重复的四元组。可以扩展三数之和：通过两个嵌套循环固定两个元素（跳过重复值），然后在内部子数组上应用双指针。时间复杂度为 O(n³)。对于一般的 k 数之和问题，该模式是递归 k-2 次，然后应用双指针，时间复杂度为 O(n^(k-1))。

def fourSum(nums, target):
    nums.sort()
    n, result = len(nums), []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, n-2):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            lo, hi = j+1, n-1
            while lo < hi:
                s = nums[i]+nums[j]+nums[lo]+nums[hi]
                if s == target:
                    result.append([nums[i],nums[j],nums[lo],nums[hi]])
                    while lo < hi and nums[lo] == nums[lo+1]: lo += 1
                    while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
                    lo += 1; hi -= 1
                elif s < target: lo += 1
                else: hi -= 1
    return result

print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

最接近目标值的两数之和

一个常见的变体是：寻找总和最接近目标值的数对（不要求严格等于目标值）。对数组排序并使用双指针。记录目前遇到的最接近总和，每当找到与目标值的绝对差更小的数对时就更新它。排序后，这种 O(n log n) 的方法很容易实现。

def twoSumClosest(nums, target):
    nums.sort()
    lo, hi  = 0, len(nums) - 1
    best    = float('inf')
    best_pair = None
    while lo < hi:
        s = nums[lo] + nums[hi]
        if abs(s - target) < abs(best - target):
            best = s
            best_pair = (nums[lo], nums[hi])
        if s < target:
            lo += 1
        elif s > target:
            hi -= 1
        else:
            return best_pair  # exact match
    return best_pair

print(twoSumClosest([1, 3, 4, 7, 10], 15))  # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10))     # (2, 8) => 10, exact!

包含多个数对的两数之和（所有数对）

要找出总和为目标值的所有数对，请先对数组排序并使用双指针收集所有数对。找到有效数对后，从两端跳过重复项，再继续处理。排序需要 O(n log n)，扫描需要 O(n)，因此总复杂度为 O(n log n)。使用哈希映射收集数对也是可行的，但需要仔细处理重复项。

def twoSumAllPairs(nums, target):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    pairs  = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            pairs.append((nums[lo], nums[hi]))
            while lo < hi and nums[lo] == nums[lo+1]: lo += 1
            while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
            lo += 1; hi -= 1
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return pairs

print(twoSumAllPairs([1,1,2,3,4,4,5], 5))  # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]

统计总和小于 K 的数对

另一个变体是：统计总和小于 k 的数对数量。对数组排序，并使用双指针。当 nums[lo] + nums[hi] < k 时，所有数对 (lo, lo+1)、(lo, lo+2)、……、(lo, hi) 都有效——也就是 hi - lo 个数对。将 lo 向右移动；否则将 hi 向左移动。总时间复杂度为排序所需的 O(n log n) 加上计数所需的 O(n)。

def countPairsLessThan(nums, k):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    count  = 0
    while lo < hi:
        if nums[lo] + nums[hi] < k:
            count += hi - lo   # all (lo, lo+1)...(lo, hi) are valid
            lo += 1
        else:
            hi -= 1
    return count

print(countPairsLessThan([1, 3, 7, 11, 12], 10))  # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7))         # (2,3),(2,3) => 2... verify

使用哈希映射求两数之和：处理重复项

当同一个值可能出现多次，并且您需要统计有效数对的数量（而不仅仅是判断是否存在）时，请在映射中存储频次。对于两个元素相等的数对，频次为 f 时，数对数量为 f*(f-1)//2。对于两个元素不同的数对，则将它们各自的频次相乘。这样就能在 O(n) 的时间内统计所有有效数对。

from collections import Counter

def countTwoSumPairs(nums, target):
    freq  = Counter(nums)
    count = 0
    seen  = set()
    for x in freq:
        y = target - x
        if y in freq and (x, y) not in seen:
            if x == y:
                count += freq[x] * (freq[x] - 1) // 2
            else:
                count += freq[x] * freq[y]
            seen.add((x, y))
            seen.add((y, x))
    return count

print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...

识别两数之和模式的变体

两数之和模式会以许多不同的形式出现。当问题要求找出满足某种数值关系（和、乘积或差）的两个或更多元素时，请识别出这一模式。核心策略始终是：固定一个元素，然后在预先计算好的结构中寻找它的补数（哈希映射，或排序数组加指针）。对于 k 数之和，可以通过嵌套循环固定 k-2 个元素，再应用基本情况进行扩展。

# Summary of approaches by scenario
scenarios = [
    ('Unsorted array, any indices, one pair',   'hash map O(n) time O(n) space'),
    ('Sorted array, any indices, one pair',      'two pointers O(n) time O(1) space'),
    ('All unique pairs summing to target',        'sort + two pointers O(n log n)'),
    ('Three numbers summing to zero (3-sum)',     'sort + fix + two pointers O(n^2)'),
    ('k numbers summing to target (k-sum)',       'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
    print(f'{scenario}\n  => {approach}\n')

两数之和问题的面试沟通

在面试中遇到两数之和时，请大声说明您的思路：“我需要找到两个相加等于目标值的数字。对于每个数字 x，我需要检查 target-x 是否存在。借助哈希映射，我可以在 O(1) 时间内完成检查，因此总时间复杂度为 O(n)，空间复杂度为 O(n)。如果数组已经排序，另一种方法是使用双指针，空间复杂度为 O(1)。”请说明两种方法，并在选择之前询问是否存在空间限制。

快速检查

请测试您对本课数据结构与算法 — 编程面试准备相关概念的理解。

在交互式课程中回答

课程回顾

本课您学到了：两数之和使用哈希映射在 O(1) 时间内检查补数是否存在，从而使整体复杂度达到 O(n)，对于已排序数组，双指针可以实现 O(1) 空间复杂度，以及三数之和和四数之和可以通过排序与嵌套循环转化为两数之和，运行复杂度分别为 O(n²) 和 O(n³)。接下来我们将学习频率统计模式，以及使用 defaultdict 和 Counter 进行分组。

免费开始

用 AI 导师学习 Python — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程: 30
课程: 120

免费开始学习查看完整课程

常见问题解答