18-4Sum

100-Same Tree | Links:

题意

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Notice that the solution set must not contain duplicate quadruplets.

Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:
Input: nums = [], target = 0
Output: []

思路

• 数学题：Sum
• 在3Sum基础上添加一个循环

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        if not nums or len(nums)<4: return res
        nums.sort()
        
        # 在3sum外加一个循环：i, j, left, right四个指针
        for i in range(len(nums)-3):
            # 跳过i重复
            if i>0 and nums[i]== nums[i-1]: continue
            for j in range(i+1, len(nums)-2):
                # 跳过j重复
                if j> i+1  and nums[j] == nums[j-1]: continue
                left, right = j+1, len(nums)-1
                while left < right:
                    sum = nums[i] + nums[j] + nums[left] + nums[right]
                    if sum == target:
                        res.append([nums[i],nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left+1]: left += 1
                        while left < right and nums[right] == nums[right-1]: right-=1
                        left += 1
                        right -= 1
                    elif sum < target: left += 1
                    else: right-=1
        return res

分析:

• Time: O(n^3)
• Space: O(n)