4 Sum (Leetcode 18)
Problem Link: https://leetcode.com/problems/4sum/
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
ans=[]
n=len(nums)
for i in range(n):
for j in range(i+1,n):
st=j+1
end=n-1
summ=target-nums[i]-nums[j]
while(st<end):
if(nums[st]+nums[end]>summ):
end-=1
elif(nums[st]+nums[end]<summ):
st+=1
else:
t=[]
t.append(nums[i])
t.append(nums[j])
t.append(nums[st])
t.append(nums[end])
if t not in ans:
ans.append(t)
while(st<end and nums[st]==t[2]):
st+=1
while(st<end and nums[end]==t[3]):
end-=1
while((j+1)<n and nums[j]==nums[j+1]):
j+=1
while((i+1)<n and nums[i]==nums[i+1]):
i+=1
return ans
Last updated