leetcode_双指针 15.三数之和

15. 三数之和

• 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

• 注意：答案中不可以包含重复的三元组。

• 思路:

  1. 排序：
     首先对数组进行排序。使得相同的元素相邻，方便去重。

  2. 遍历数组：

     1). 使用一个外层循环遍历排序后的数组，固定一个数 nums[i] 作为三元组的第一个数。

     2). 在内层循环中，使用双指针法在 nums[i+1:] 中寻找另外两个数 nums[j] 和 nums[k]，使得 nums[i] + nums[j] + nums[k] == 0。

  3. 双指针法：

     1). 初始化两个指针：left = i + 1 和 right = len(nums) - 1。(对向指针)

     2). 计算当前的和 sum = nums[i] + nums[left] + nums[right]

     3). 如果 sum == 0，将其加入结果中。如果 sum < 0，说明和太小，需要增大，因此移动左指针 left += 1。如果 sum > 0，说明和太大，需要减小，因此移动右指针 right -= 1。

  4. 去重：

     1). 在外层循环中，如果 nums[i] 和前一个数相同（即 nums[i] == nums[i-1]），则跳过，避免重复。

     2). 在内层循环中，找到满足条件的三元组后，跳过所有相同的 nums[left] 和 nums[right]，避免重复。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()  # 排序
        result = []
        n = len(nums)
        
        for i in range(n - 2):  # 外层循环，固定 nums[i]
            if i > 0 and nums[i] == nums[i - 1]:  # 去重
                continue
            
            left, right = i + 1, n - 1  # 双指针
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:  # 找到满足条件的三元组
                    result.append([nums[i], nums[left], nums[right]])
                    # 去重
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    # 移动指针
                    left += 1
                    right -= 1
                elif total < 0:  # 和太小，移动左指针
                    left += 1
                else:  # 和太大，移动右指针
                    right -= 1
        
        return result

• 时间复杂度：排序: O(nlogn), 双重循环遍历: O(n^2)
  总时间复杂度为 O(n^2)

• 空间复杂度： O(1)（不考虑结果数组）