forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbhyun-kim.py
More file actions
83 lines (66 loc) Β· 2.19 KB
/
bhyun-kim.py
File metadata and controls
83 lines (66 loc) Β· 2.19 KB
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
"""
15. 3Sum
https://leetcode.com/problems/3sum/description/
Solution:
- Sort the list
- Iterate through the list
- For each element, find the two elements that sum up to -element
- Use two pointers to find the two elements
- Skip the element if it is the same as the previous element
- Skip the two elements if they are the same as the previous two elements
- Add the set to the output list
Example:
-----------------------------------------
low : |
high: |
i : |
[-4,-1,-1,0,1,2]
-----------------------------------------
low : |
high: |
i : |
[-4,-1,-1,0,1,2]
... no possible set with i=-4, and high=2
-----------------------------------------
low : |
high: |
i : |
[-4,-1,-1,0,1,2]
Time complexity: O(n^2)
- O(nlogn) for sorting
- O(n^2) for iterating through the list and finding the two elements
- Total: O(n^2)
Space complexity: O(n)
- O(n) for the output list
- O(n) for the prevs dictionary
- O(n) for the prevs_n set
- Total: O(n)
"""
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
output = []
prevs = dict()
prevs_n = set()
for i in range(len(nums) - 2):
n_i = nums[i]
if n_i in prevs_n:
continue
else:
prevs_n.add(n_i)
low, high = i + 1, len(nums) - 1
while low < high:
n_low = nums[low]
n_high = nums[high]
if n_i + n_low + n_high == 0:
if not f"[{n_i},{n_low},{n_high}]" in prevs:
prevs[f"[{n_i},{n_low},{n_high}]"] = 1
output.append([n_i, n_low, n_high])
low += 1
high -= 1
elif n_i + n_low + n_high < 0:
low += 1
elif n_i + n_low + n_high > 0:
high -= 1
return output