Can anyone tell me whats wrong with my code?


  • 0
    S

    4Sum. It says Time Limit Exceeded. But I think the time complexity of my algorithm is O(n^3). The basic idea is to make j, k as two pointers and check if the four add up to the target.

    class Solution(object):
        def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            nums = sorted(nums)
            zero_list = []
            for i in range(len(nums)-3):
                if(i>0 and nums[i] == nums[i-1]):
                    continue
                for s in range(i+1, len(nums)-2):
                    if(s-i>1 and nums[s] == nums[s-1]):
                        continue
                    j = s + 1
                    k = len(nums)-1
                    while j < k:
                        if nums[i]+nums[s]+nums[j]+nums[k] == target:
                            zero_list.append((nums[i], nums[s], nums[j], nums[k]))
                            
                            while nums[j] == nums[j+1] and j+1 < k:
                                j += 1
                            while nums[k] == nums[k-1] and k-1 > j:
                                k -= 1
                            j += 1
                            k -= 1
                        elif nums[i]+nums[s]+nums[j]+nums[k] < target:
                            j += 1
                        else:
                            k -= 1
            return zero_list

  • 1
    H

    Your code could still be optimized, add following would be Ok
    if 2nums[j]>target-nums[i]-nums[s] or 2nums[k]<target-nums[i]-nums[s] : break


Log in to reply
 

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