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