跳到主要内容

两数之和

问题​

给定一个整数数组 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(n²) - 两层循环
  • 空间复杂度：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) - 最坏情况下需要存储 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(n²)O(1)✅
哈希表O(n)O(n)✅
排序+双指针O(n log 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;
}

面试要点​

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

相关链接​