leetcode 15. 三数之和

发表于 分类于 阅读次数：

解题思路

利用双指针将时间复杂度从O(N^3)降为O(N^2)

时间复杂度

O(N^2)

空间复杂度

O(N)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = []

        nums_len = len(nums)
        if nums_len < 3:
            return ret
            
        nums.sort()
        for i, num in enumerate(nums):
            if num > 0:
                break
            if i > 0 and num == nums[i-1]:
                continue
            left = i + 1
            right = nums_len - 1
            while left < right:
                total = num + nums[left] + nums[right]
                if total == 0:
                    ret.append([num, nums[left], nums[right]])
                    while left < right and nums[left+1] == nums[left]:
                        left += 1
                    while right > left and nums[right-1] == nums[right]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total > 0:
                    right -= 1
                else:
                    left += 1
        
        return ret