[LeetCode][python3]0018. 4Sum

  1. My first try
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
ans=[]
nums=sorted(nums)
for a,tar_a in enumerate(nums[:-3]):
b=a+1
for tar_b in nums[a+1:-2]:
c=b+1
d=len(nums)-1
while d>c:
#print(a,b,c,d)
tar_c=nums[c]
tar_d=nums[d]
if tar_a+tar_b+tar_c+tar_d==target:
if [tar_a,tar_b,tar_c,tar_d] not in ans:
ans.append([tar_a,tar_b,tar_c,tar_d])
else:
c+=1
d-=1
elif tar_a+tar_b+tar_c+tar_d>target:
d-=1
else:
c+=1
b+=1
return ans
N2I -2020.04.02
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if not nums:
return []
nums = sorted(nums)
res = []
self.kSum(nums, 0, len(nums)-1, 4, target, [], res)
return res


def kSum(self, nums, left, right, k, target, state, res):
# not enough
if k < 2 or right - left + 1 < k:
return
if k * nums[left] > target or k * nums[right] < target:
return
if k == 2:
# reduce to 2 sum problem
while left < right:
cur = nums[left] + nums[right]
if cur == target:
res.append(state + [nums[left], nums[right]])
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
elif cur > target:
right -= 1
else:
left += 1
else:
# k > 2, reduce the degree
for i in range(left, right+1):
if i == left or i > left and nums[i] != nums[i-1]:
self.kSum(nums, i+1, right, k-1, target-nums[i], state+[nums[i]], res)
N2I -2020.04.02
class Solution:
def fourSum(self, nums, target):
if not nums:
return []
nums=sorted(nums)
numsLen = len(nums)
dic = {j:i for i, j in enumerate(nums)}
ans = set()
N = nums[-1]
for idx, num1 in enumerate(nums[:-3]):
if num1 + 3 * N < target:
continue
if 4 * num1 > target:
break
for j in range(idx + 1, numsLen - 2):
num2 = nums[j]
if num1 + num2 + 2 * N < target:
continue
if num1 + 3 * num2 > target:
break
for k in range(j + 1, numsLen - 1):
c = nums[k]
temp = target - num1 - num2 - c
if temp > N:
continue
if temp < c:
break
if temp in dic and dic[temp] > k:
ans.add((num1, num2, c, temp))
return ans
N2I -2020.04.02

--

--

--

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to add Image Cropper in ionic 4 app

How to add Image Cropper in ionic 4 app

Data Analytics platform to track SaaS Usage & Billing —  Metered Billing

Web1 vs Web2 vs Web3, in a nutshell

Building Android Projects on CircleCi (using their Machine Executor)

Is Arduino that much easy for you?

Create and publish your own Python package

Invoking a Serverless “Hello World” Lambda Function

How I Taught Myself to Print Gold and Launch A Jewelry Line

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
N2I

N2I

HI I’m N2I. Now a SWE in Taiwan. Check out more about me in https://nzi2020.blogspot.com/ or contact via email: nayzi9999@gmail.com

More from Medium

Hackerrank — Reverse Doubly Linked List walkthrough #Python #Hackerrank

Bubble Sort Algorithm using Java

39. Combination Sum

2D Array DS Hackerrank solution in Python