跳到主要内容

两数之和

问题​

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

示例：

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

答案​

方法一：暴力枚举​

最直观的方法是使用两层循环，遍历所有可能的组合：

function twoSum(nums: number[], target: number): number[] {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}
复杂度分析
  • 时间复杂度：O(n2)O(n^2) - 两层循环
  • 空间复杂度：O(1)O(1) - 只使用常数额外空间

这种方法效率较低，不推荐在面试中使用。

方法二：哈希表（推荐）​

使用哈希表存储已遍历的元素及其索引，实现一次遍历：

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }

    map.set(nums[i], i);
  }

  return [];
}
核心思路

遍历数组时，对于每个元素 nums[i]：

  1. 计算它的"补数" complement = target - nums[i]
  2. 检查哈希表中是否存在这个补数
  3. 如果存在，直接返回结果
  4. 如果不存在，将当前元素存入哈希表

复杂度分析：

  • 时间复杂度：O(n)O(n) - 只需要遍历一次数组
  • 空间复杂度：O(n)O(n) - 最坏情况下需要存储 n-1 个元素

方法三：排序 + 双指针​

如果允许返回元素值而非索引，可以使用双指针：

function twoSumValues(nums: number[], target: number): number[] {
  const sorted = [...nums].sort((a, b) => a - b);
  let left = 0;
  let right = sorted.length - 1;

  while (left < right) {
    const sum = sorted[left] + sorted[right];

    if (sum === target) {
      return [sorted[left], sorted[right]];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return [];
}
适用场景

双指针方法适用于：

  • 数组已排序
  • 只需要返回元素值，不需要原始索引
  • 需要找出所有满足条件的组合

方法对比​

方法时间复杂度空间复杂度是否保留索引
暴力枚举O(n2)O(n^2)O(1)O(1)✅
哈希表O(n)O(n)O(n)O(n)✅
排序+双指针O(nlog⁡n)O(n \log n)O(n)O(n)❌

变体问题​

1. 返回所有组合​

function twoSumAll(nums: number[], target: number): number[][] {
  const result: number[][] = [];
  const map = new Map<number, number[]>();

  // 先收集所有元素的索引
  nums.forEach((num, index) => {
    if (!map.has(num)) {
      map.set(num, []);
    }
    map.get(num)!.push(index);
  });

  const seen = new Set<string>();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    const indices = map.get(complement);

    if (indices) {
      for (const j of indices) {
        if (i !== j) {
          const pair = [Math.min(i, j), Math.max(i, j)];
          const key = pair.join(',');
          if (!seen.has(key)) {
            seen.add(key);
            result.push(pair);
          }
        }
      }
    }
  }

  return result;
}

2. 三数之和（LeetCode 15）​

function threeSum(nums: number[], target: number = 0): number[][] {
  const result: number[][] = [];
  const sorted = [...nums].sort((a, b) => a - b);
  const n = sorted.length;

  for (let i = 0; i < n - 2; i++) {
    // 跳过重复元素
    if (i > 0 && sorted[i] === sorted[i - 1]) continue;

    let left = i + 1;
    let right = n - 1;

    while (left < right) {
      const sum = sorted[i] + sorted[left] + sorted[right];

      if (sum === target) {
        result.push([sorted[i], sorted[left], sorted[right]]);
        // 跳过重复元素
        while (left < right && sorted[left] === sorted[left + 1]) left++;
        while (left < right && sorted[right] === sorted[right - 1]) right--;
        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

常见面试问题​

Q1: 为什么哈希表解法比暴力解法快？​

答案：

// 暴力解法：对于每个元素，都要遍历剩余所有元素
// 第一个元素需要比较 n-1 次
// 第二个元素需要比较 n-2 次
// ...总共 (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²)

// 哈希表解法：每个元素只需要一次哈希查找 O(1)
// 总共 n 个元素，所以是 O(n)

核心优化：用空间换时间，把已遍历的元素存入哈希表，实现 O(1)O(1) 查找。

Q2: 为什么是"先查找再存入"而不是"先存入再查找"？​

答案：

// ✅ 正确：先查找再存入
for (let i = 0; i < nums.length; i++) {
  const complement = target - nums[i];
  if (map.has(complement)) {
    return [map.get(complement)!, i];
  }
  map.set(nums[i], i);  // 之后才存入
}

// ❌ 错误：先存入再查找
for (let i = 0; i < nums.length; i++) {
  map.set(nums[i], i);  // 先存入
  const complement = target - nums[i];
  if (map.has(complement)) {
    // 可能找到自己！如 nums=[3], target=6
    // complement=3, 但 3 是自己
  }
}

原因：题目要求不能使用两次相同的元素。如果先存入，可能会找到自己。

Q3: 如果数组中有重复元素怎么办？​

答案：

哈希表存储的是最后一次出现的索引，但这不影响正确性：

// nums = [3, 3], target = 6
// 遍历第一个 3：map 为空，存入 {3: 0}
// 遍历第二个 3：找到 complement=3 在 map 中，返回 [0, 1]

// 因为是"先查找再存入"，所以：
// - 如果两个相同的数相加等于 target，能找到
// - 如果只有一个数的两倍等于 target，不会错误返回

Q4: 这道题能用双指针吗？​

答案：

可以，但有限制：

function twoSumSorted(nums: number[], target: number): number[] {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return [];
}

限制：

  1. 数组必须已排序
  2. 只能返回元素值，不能返回原始索引（排序后索引变了）

如果要返回原始索引：

function twoSum(nums: number[], target: number): number[] {
  // 保存原始索引
  const indexed = nums.map((v, i) => ({ v, i }));
  indexed.sort((a, b) => a.v - b.v);

  let left = 0, right = indexed.length - 1;
  while (left < right) {
    const sum = indexed[left].v + indexed[right].v;
    if (sum === target) {
      return [indexed[left].i, indexed[right].i];
    }
    // ...
  }
}

Q5: 如何扩展到三数之和、四数之和？​

答案：

三数之和（LeetCode 15）：

  • 固定一个数，转化为两数之和
  • 排序 + 双指针，注意去重
function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;  // 去重

    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++; right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return result;
}

通用思路：k 数之和 = 固定一个数 + (k-1) 数之和

面试要点​

面试技巧
  1. 先提出暴力解法，展示思路
  2. 分析暴力解法的问题，引出优化方案
  3. 说明哈希表如何将时间复杂度从 O(n2)O(n^2) 降到 O(n)O(n)
  4. 主动提及边界情况（空数组、无解等）
  5. 如果时间允许，讨论变体问题

相关链接​