[Help] [Python] Why my solution is so slow?


  • 0

    I have attached my solution below, which is simply a iterative version of this recursive method. However, the recursive method is pretty fast (180 ms) while mine solution is very inefficient (1200 ms). Any idea what is causing the inefficiency? Any suggestion would be super helpful. Many thanks!

    def fourSum(self, nums, target):
        nums.sort()
        res,n = [],len(nums)
        for i in range(n-3):
            if i == 0 or nums[i] != nums[i-1]:
                for j in range(i+1,n-2):
                    if j == i+1 or nums[j] != nums[j-1]:
                        ntarget = target-nums[i]-nums[j]
                        l,r = j+1,n-1
                        while l < r:
                            if l == j+1 or nums[l-1] != nums[l]:
                                if nums[l]+nums[r]==ntarget:
                                    res.append([nums[i],nums[j],nums[l],nums[r]])
                                    l += 1
                                    r -= 1
                                elif nums[l]+nums[r]>ntarget:
                                    r -= 1
                                else:
                                    l += 1
                            else:
                                l += 1
        return res

Log in to reply
 

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