Question about Pyhthon solution TLE for Ksum


  • 0
    G
    class Solution(object):
        def fourSum(self, nums,target):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            res = []
            nums.sort()
            self.dfs(nums,4,target,0,[],res)
            return res
            
        def dfs(self,nums,n,target,index,temp,res):
            if n==0 :
                if target==0:
                    res.append(temp)
                return 
            for i in range(index,len(nums)-n+1):
                if i>index and nums[i]==nums[i-1]:continue
                self.dfs(nums,n-1,target-nums[i],i+1,temp+[nums[i]],res)
            return
    
    

    Well,this is my python solution using dfs, but unluckily it got TLE, and the AC solution for Ksum:

    lass Solution(object):
        def fourSum(self, nums,target):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            res = []
            nums.sort()
            self.dfs(nums,4,target,0,[],res)
            return res
            
        def dfs(self,nums,n,target,index,temp,res):
            if len(nums)-index<n or n<2:return
            if n==2:
                l,r=index,len(nums)-1
                while l<r:
                    if nums[l]+nums[r]==target:
                        res.append(temp+[nums[l],nums[r]])
                        l+=1
                        r-=1
                        while l<r and nums[r]==nums[r+1]:r-=1
                        while l<r and nums[l]==nums[l-1]:l+=1
                    elif nums[l]+nums[r]<target:
                        l+=1
                    else:
                        r-=1
                return
            else:
                for i in range(index,len(nums)-n+1):
                    if i>index and nums[i]==nums[i-1]:continue
                    self.dfs(nums,n-1,target-nums[i],i+1,temp+[nums[i]],res)
            return
    

    We can find the difference is only the exit ,(n==0 and n==2), my question is why n==2 works? Can anyone help? Thanks :-)


Log in to reply
 

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