Python O(n^3)


  • 0

    1 + 3Sum

    class Solution(object):
        def fourSum(self, nums, target):
            nums.sort()
            ans, i = [], 0
            while i < len(nums) - 3:
                j = i + 1
                while j < len(nums) - 2:
                    left, right = j + 1, len(nums) - 1
                    while left < right:
                        tmp = nums[i] + nums[j] + nums[left] + nums[right]
                        if tmp > target:
                            right -= 1
                        elif tmp < target:
                            left += 1
                        else:
                            ans.append([nums[i], nums[j], nums[left], nums[right]])
                            while left < right and nums[left + 1] == nums[left]:
                                left += 1
                            while left < right and nums[right - 1] == nums[right]:
                                right -= 1
                            left, right = left + 1, right - 1
                    while j + 1 < len(nums) - 2 and nums[j + 1] == nums[j]:
                        j += 1
                    j += 1
                while i + 1 < len(nums) - 3 and nums[i + 1] == nums[i]:
                    i += 1
                i += 1
            return ans 
    

Log in to reply
 

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