[LCD2][双指针]15.三数之和

题目分析

题目要求在整数数组 nums 中找出所有不重复的三元组 [nums[i], nums[j], nums[k]]，使得 nums[i] + nums[j] + nums[k] == 0，同时满足 i != j != k。关键点在于如何有效地找出所有满足条件的三元组，同时避免产生重复的三元组。

解题思路

1. 排序： 首先对数组进行排序，这样可以使相同的数字聚集在一起，便于后续去重。

2. 递归分解： 将三数之和的问题分解为多个两数之和的问题。我们使用一个递归函数 nSum，在每一层递归中解决一个数之和的问题，直到降解到两数之和。

3. 两数之和： 使用双指针方法解决两数之和的问题，通过移动指针来寻找和为目标值的数对。

4. 去重： 在每一层递归中，以及在解决两数之和问题时，都需要注意去重。

代码解释

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 对数组排序
        return self.nSum(nums, 3, 0, 0)  # 调用递归函数

    def nSum(self, nums: List[int], n: int, start: int, target: int) -> List[List[int]]:
        length = len(nums)
        res = []

        if n < 2 or length < n:
            return res

        if n == 2:  # 当问题降解到两数之和
            l, r = start, length - 1
            while l < r:
                s = nums[l] + nums[r]
                left, right = nums[l], nums[r]
                if s < target:  # 移动左指针
                    while l < r and nums[l] == left:
                        l += 1
                elif s > target:  # 移动右指针
                    while l < r and nums[r] == right:
                        r -= 1
                else:  # 找到目标组合，去重并记录
                    res.append([left, right])
                    while l < r and nums[l] == left:
                        l += 1
                    while l < r and nums[r] == right:
                        r -= 1
        else:  # 当处理更多数之和问题
            i = start
            while i < length:  # 遍历并去重
                sub = self.nSum(nums, n - 1, i + 1, target - nums[i])
                for arr in sub:
                    arr.append(nums[i])
                    res.append(arr)
                while i < length - 1 and nums[i] == nums[i + 1]:
                    i += 1
                i += 1
        return res

在初次尝试时，选择了 for 循环来遍历数组。然而，当需要在循环中调整迭代器（例如跳过重复元素）时，for 循环由于其自动递增的特性，会导致跳过某些未处理的元素。 使用 while 循环可以更精确地控制迭代过程。当使用 while 循环时，可以在发现重复元素时手动控制迭代器的增加，从而确保每个元素都被恰当地处理。

时间复杂度和空间复杂度分析

• 时间复杂度：

  • 排序的时间复杂度为 (O(N \log N))。
  • nSum 函数中，对于每个元素，我们都在剩余元素上进行一次两数之和的操作，其时间复杂度为 (O(N))。由于 nSum 是递归的，总的时间复杂度为 (O(N^2))。

• 空间复杂度：

  • 主要空间消耗来自排序算法，通常为 (O(\log N))。
  • 递归栈的空间复杂度取决于递归的深度，这里为 (O(N))。

总的来说，这个算法的时间复杂度主要为 (O(N^2))，空间复杂度为 (O(N))。