[LeetCode] 18. 4Sum

Problem : https://leetcode.com/problems/4sum/

Similar to 3Sum.

Time Complexity : O ( len(nums) *len(nums) * len(nums)/2 )

Space Complexity: O (len(nums)*len(nums)*len(nums)*len(nums))

 
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        nums.sort()
        L = len(nums)
        
        result = []
        
        for i in range(L-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            for j in range(i+1, L-2):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                    
                left, right = j + 1, L - 1
                
                while left < right:
                    # early termination
                    if nums[i] + nums[j] + nums[left] + nums[left] > target:
                        break
                        
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if tmp < target:
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                    elif tmp > target:
                         l = right - 1
                         while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                         right = l
                    else:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                        
                        l = right - 1
                        while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                        right = l
                        
        return result