-
Notifications
You must be signed in to change notification settings - Fork 0
/
18) 4 Sums.py
47 lines (39 loc) · 1.56 KB
/
18) 4 Sums.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
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
results = []
self.helper(nums, target, 4, [], results)
return results
def helper(self, nums, target, N, res, results):
if len(nums) < N or N < 2: #1
return
if N == 2: #2
output_2sum = self.twoSum(nums, target)
if output_2sum != []:
for idx in output_2sum:
results.append(res + idx)
else:
for i in range(len(nums) -N +1): #3
if nums[i]*N > target or nums[-1]*N < target: #4
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: #5
self.helper(nums[i+1:], target-nums[i], N-1, res + [nums[i]], results)
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = []
left = 0
right = len(nums) - 1
while left < right:
temp_sum = nums[left] + nums[right]
if temp_sum == target:
res.append([nums[left], nums[right]])
right -= 1
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while right > left and nums[right] == nums[right + 1]:
right -= 1
elif temp_sum < target:
left +=1
else:
right -= 1
return res