qiyu-lu

个人记录

1 minute read

LeetCode 15. 三数之和 (3Sum)

核心问题

在一个数组中找出所有和为 0 且不重复的三元组。

思路演进：如何想到最优解？

解决这类问题的通常思路是从暴力解法开始，逐步优化，最终得到高效的解法。

阶段一：暴力求解 (O(n³))

最直观的想法是穷举所有可能。用三层循环遍历数组，找出所有三个数的组合，判断它们的和是否为 0。

  • 伪代码: 
    for i from 0 to n-1:
  for j from i+1 to n-1:
    for k from j+1 to n-1:
      if nums[i] + nums[j] + nums[k] == 0:
        add (nums[i], nums[j], nums[k]) to result
  • 问题:
    1. 时间复杂度太高: O(n³) 无法通过大多数测试用例。
    2. 重复问题: 需要额外的数据结构（如 HashSet）对结果进行去重，增加了复杂性。

阶段二：降维 -> “2Sum” 问题 (O(n²))

为了降低复杂度，我们可以尝试减少一层循环。思路是“固定一个数，找另外两个数”。

我们遍历数组，固定第一个数 nums[i]，那么问题就转化为：在数组的剩余部分中寻找两个数，使它们的和等于 -nums[i]。这就把“3Sum”问题降维成了我们熟悉的“2Sum”问题。

如何解决这个内部的“2Sum”问题？

  1. 哈希表法: 遍历 nums[i] 之后的部分，对于每个 nums[j]，我们去哈希表中查找是否存在 target - nums[j]（其中 target = -nums[i]）。这方法可行，整体时间复杂度为 O(n²)，空间复杂度为 O(n)。（这对应了 threeSumBF 方法的思路）。
  2. 双指针法: 如果数组是有序的，解决“2Sum”问题会更高效。这就是我们走向最优解的关键一步。

阶段三：排序 + 双指针 (最优解 O(n²))

结合“降维”和“有序数组”这两个思想，最终的解法浮出水面。

  1. 排序 (Sort): 首先对整个数组进行排序，时间复杂度 O(n log n)。排序是使用双指针的前提，并且极大地简化了去重操作。

  2. 遍历与固定 (Outer Loop): 遍历排序后的数组，用 for 循环固定第一个数 nums[i]。

  3. 双指针 (Inner Two Pointers): 在 nums[i] 后面的区间 [i+1, n-1] 上，设置左指针 left = i + 1 和右指针 right = n - 1。
    • 计算三数之和 sum = nums[i] + nums[left] + nums[right]。
    • 如果 sum == 0，说明找到了一个解。记录下来，然后同时移动 left 和 right 指针并跳过所有重复元素，继续寻找其他解。
    • 如果 sum < 0，说明和太小了，需要增大。因为数组是有序的，所以移动左指针 left++。
    • 如果 sum > 0，说明和太大了，需要减小。移动右指针 right--。
  4. 去重 (Deduplication):
    • 外层循环去重: 当我们固定 nums[i] 时，如果 i > 0 且 nums[i] 和它前一个数 nums[i-1] 相等，说明以 nums[i] 开头能找到的三元组，之前以 nums[i-1] 开头时肯定都已经找到了。因此可以直接跳过，避免重复计算。
    • 内层指针去重: 当 sum == 0 找到一个解后，需要将 left 和 right 指针移动到下一个不重复的位置，以防同一个三元组被多次记录。

这个“排序 + 双指针”的方案，将时间复杂度降到了 O(n²)，空间复杂度为 O(1)（不考虑结果存储空间），是此问题的最佳解法。

举一反三：从 “3Sum” 到 “K-Sum”

这个“排序 + N指针”的思路可以推广到更一般性的“K-Sum”问题。

  • 2Sum (K=2):
    • 哈希表法: O(n) 时间, O(n) 空间。
    • 排序+双指针法: O(n log n) 时间, O(1) 空间。
  • 3Sum (K=3):
    • 转化为 2Sum: O(n²) 时间。for + two_pointers。
  • 4Sum (K=4):
    • 转化为 3Sum: O(n³) 时间。for + 3Sum_logic，即 for + for + two_pointers。
    • 通用解法: 固定第一个数，递归调用 3Sum；或者固定前两个数，在剩余部分做 2Sum。
  • K-Sum (通用):
    • 递归思路: 
        function kSum(nums, target, k):
// 提前剪枝
if a few base cases fail, return []
      
if k == 2:
  return twoSum(nums, target) // 双指针解决
        
for i from 0 to n-1:
  // 去重
  if i > 0 and nums[i] == nums[i-1]:
    continue
            
  // 递归调用 (k-1)Sum
  sub_results = (k-1)Sum(nums[i+1:], target - nums[i], k-1)
          
  // 组合结果
  for res in sub_results:
    result.add([nums[i]] + res)
        
return result
    • 在每层递归中，都需要排序（或利用已排序的数组）和去重逻辑。通过这种递归+双指针的模式，可以将 K-Sum 问题在 O(n^(k-1)) 的时间复杂度内解决。

You May Also Enjoy