三数之和

LeetCode 三数之和题解，使用排序+双指针将时间复杂度从O(n^3)优化到O(n^2)，并处理重复三元组。

Leetcode 双指针排序算法 Python

题目

https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked

解法

思路

若按照无序数组来做，至少需要O(n^3)的时间复杂度。

因此可以先进行一个排序（O(nlogn)）,引入大小排序。

当确定第i个数后，可以类似于盛水容器的双指针移动思路：三数之和大于0，则右指针向左移动，小于0，则左指针向右移动。 原因：因为是有序的

注意：因为题目中说了相同的三元组只能出现一次，因此需要注意遇到相同数时，除了第一个其余都要跳过

答案

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums_sorted = sorted(nums)
        res = []
        for i in range(len(nums_sorted)):
            if i > 0 and nums_sorted[i] == nums_sorted[i-1]:
                continue
            l = i + 1
            r = len(nums_sorted) - 1
            while l < r:
                sum = nums_sorted[i] + nums_sorted[l] + nums_sorted[r]
                if sum > 0:
                    r -= 1
                elif sum < 0:
                    l += 1
                else:
                    res.append([nums_sorted[i] , nums_sorted[l] , nums_sorted[r]])
                    while l < r and nums_sorted[l] == nums_sorted[l+1]:
                        l += 1
                    while l < r and nums_sorted[r] == nums_sorted[r-1]:
                        r -= 1
                    r -= 1
                    l += 1
 
        return res