leetcode/015_3Sum.py at master · annabechang/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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
"""
15. 3Sum
Medium

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
"""
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        nums.sort()

        for i in range(n-2):
            #n-2 bec/ if i = n-2 ~ n, it's meaningless to set i to n-1 and n since there won't be enough numbers
            # if i=0~ 2 > 0 means there's not enough - numbers
            if nums[i] + nums[i+1] + nums[i+2] > 0:
                break
            # if i = -100, -2 ~ 8,9 move from i = -100 to i = -2
            if nums[i] + nums[n-2] + nums[n-1] < 0:
                continue
            if i > 0 and nums[i] == nums[i-1]:
                continue

            l, r = i+1, n-1
            # it will break when l=r
            while l < r:
                tmp = nums[i] + nums[l] + nums[r]
                if tmp == 0:
                    result.append([nums[i], nums[l], nums[r]])
                    #make sure you're getting different number
                    while l+1 < r and nums[l] == nums[l+1]:
                        l += 1
                    l +=1
                    while r-1 > l and nums[r] == nums[r-1]:
                        r -= 1
                    r -= 1
                elif tmp < 0:
                    l +=1
                else:
                # tmp > 0:
                    r -= 1
        return result

"""
Success
Details
Runtime: 736 ms, faster than 84.99% of Python3 online submissions for 3Sum.
Memory Usage: 17 MB, less than 27.86% of Python3 online submissions for 3Sum.

"""


"""
two pointer method
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):

            if i>0 and nums[i-1] == nums[i]:
                continue

            l = i+1
            r = len(nums)-1
            # print(nums[i],nums[l],nums[r])
            while l<r:
                s = nums[i]+nums[l]+nums[r]
                # print(nums[i],nums[l],nums[r])
                if  s>0:
                    r-=1
                    # print("el2",nums[i],nums[l],nums[r])
                elif s < 0:
                    l+=1
                    # print("el1",nums[i],nums[l],nums[r])


                else:
                    # s == 0:
                    res.append([nums[i],nums[l],nums[r]])
                    l+=1
                    #this while loop is to skip duplicates
                    while nums[l-1] == nums[l] and l<r:
                        l+=1
                    # print("el0",nums[i],nums[l],nums[r])


        return res
        """