-
Notifications
You must be signed in to change notification settings - Fork 0
/
3_sum.py
100 lines (76 loc) · 2.58 KB
/
3_sum.py
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
from sys import stdin
def inp():
return stdin.readline().rstrip()
def iinp():
return int(inp())
def mp():
return map(int, inp().split())
def liinp():
return list(mp())
def three_sum(nums):
# This solution is 904ms sur LC 👍
# get the length of input list: nums
length = len(nums)
# sort input numbers, to keep the increasing order
nums.sort()
# container for 3 sum answer storage
triplet_answer = list()
# length - 2 is for the valid index i, j ,k within boundary
# i = index for the first element such that 3 sum = nums[i] + nums[j] + nums[k] = 0
for i in range(0, length-2):
# skip the repetition of the same element (the limitation of problem description)
if i>0 and (nums[i-1]==nums[i]):
continue
# j : index for the second element such that 3 sum = nums[i] + nums[j] + nums[k] = 0
# start from smallest value after index i
# k : index for the third element such that 3 sum = nums[i] + nums[j] + nums[k] = 0
# start from largest value after index i
j , k = i+1, length-1
# inner loop to iterate index j, k
while j<k :
three_sum = nums[i]+nums[j]+nums[k]
# check index i, j , k meets the sum value = 0 or not
if three_sum==0:
# get one triplet satisfy requirement, append to triplet_answer
triplet_answer.append([nums[i], nums[j], nums[k]])
# update index j, k for next iteration
j += 1
k -= 1
# skip the repetition of the same element
while j<k and (nums[j]==nums[j-1]): # Pour ne pas avoir les mêmes resulats
j += 1
# skip the repetition of the same element
while j<k and (nums[k]==nums[k+1]): # Pour ne pas avoir les mêmes resulats
k -= 1
elif three_sum<0:
# sum value is too small, make the second element larger on next iteration
# update index j
j += 1
else:
# sum value is too big, make the third element smaller on next iteration
# update index k
k -= 1
# return the container for 3 sum triplet
return triplet_answer
"""
# This solution is 6000+ms sur LC 👎
nums.sort()
three_triplet = []
for i in range(len(nums)-2):
left = i + 1
right = len(nums) - 1
while left < right:
if nums[left] + nums[right] > -nums[i]:
right -= 1
elif nums[left] + nums[right] < -nums[i]:
left += 1
else:
three_sum_triplet = [nums[i], nums[left], nums[right]]
if three_sum_triplet not in three_triplet:
three_triplet.append(three_sum_triplet)
left += 1
return three_triplet
"""
if __name__ == "__main__":
nums = [-1,0,1,2,-1,-4,-2,-3,3,0,4]
print(three_sum(nums))