[数据结构与算法]力扣18题四数之和

题目描述

给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在4个元素a、b、c、d，使a+b+c+d的值与target相等？找出所有满足条件且不重复的四元组。

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        results=[]
        self.findNsum(nums,target,4,[],results)
        return results
    def findNsum(self,nums,target,N,tempList,results):
        if len(nums)<N or N<2:
            return
        if N==2:
            l=0
            r=len(nums)-1
            while l<r:
                if nums[l]+nums[r]==target:
                    results.append(tempList+[nums[l],nums[r]])
                    l+=1
                    r-=1
                    while l<r and nums[l]==nums[l-1]:
                        l+=1
                    while l<r and nums[r]==nums[r+1]:
                        r-=1
                elif nums[l]+nums[r]<target:
                    l+=1
                else:
                    r-=1
        else:
            for i in range(0,len(nums)):
                if i==0 or i>0 and nums[i-1] !=nums[i]:
                    self.findNsum(nums[i+1:],target-nums[i],N-1,tempList+[nums[i]],results)
        return

复杂度分析

●　时间复杂度：O(n3)。
●　空间复杂度：本算法的空间消耗主要由tempList、调用栈和排序算法这3块组成。和tempList的空间消耗相比，调用栈及排序算法产生的空间消耗更少，因此空间复杂度为O(n)，其中n为数组长度。