LeetCode/15.3Sum.py at master · tobyatgithub/LeetCode · GitHub

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
33
34
35
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sortedNums = sorted(nums)
        i = 0
        res = []

        while i < len(sortedNums):
            if i > 0 and sortedNums[i] == sortedNums[i - 1]:
                i += 1
                continue
            qualifiedPairs = self.twoSum(sortedNums[i + 1 :], sortedNums[i])
            if qualifiedPairs:
                print(qualifiedPairs)
                res.extend(qualifiedPairs)
            i += 1

        return res

    def twoSum(self, sortedNums, target):
        l, r = 0, len(sortedNums) - 1
        res = []
        while l < r:
            numL = sortedNums[l]
            numR = sortedNums[r]
            if numL + numR + target == 0:
                toAdd = [numL, numR, target]
                if toAdd not in res:
                    res.append(toAdd)
                l += 1
                # r -= 1
            if numL + numR + target < 0:
                l += 1
            if numL + numR + target > 0:
                r -= 1
        return res