my simple python solution O(n**3)


  • 0
    N
    class Solution(object):
        def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            ret_list = []
            if not nums or len(nums) < 4:
                return ret_list
            
            nums.sort()
            length = len(nums)
            for i in xrange(length - 3):
                "too big"
                if 4*nums[i] > target:
                    return ret_list
                "too small"
                if nums[i] + 3*nums[length - 1] < target:
                    continue
                "avoid duplicate"
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                    
                for j in xrange(i+1, length - 2):
                    "avoid duplicate"
                    if j > i + 1 and nums[j] == nums[j - 1]:
                        continue
                    "too big"
                    if nums[i] + 3*nums[j] > target:
                        break
                    "too small"
                    if nums[i] + nums[j] + 2*nums[length - 1] < target:
                        continue
                        
                    k = j + 1
                    l = length - 1
                    while k < l:
                        if nums[i] + nums[j] + 2*nums[k] > target:
                            break
                        total = nums[i] + nums[j] + nums[k] + nums[l]
                        if total == target:
                            new_list = [nums[i], nums[j], nums[k], nums[l]]
                            ret_list.append(new_list)
                            k += 1
                            l -= 1
                            
                            while k < l and nums[k] == nums[k - 1]:
                                k += 1
                            while k < l and nums[l] == nums[l + 1]:
                                l -= 1
                            
                        elif total > target:
                            l -= 1
                        else:
                            k += 1
            
            return ret_list
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.