18.4Sum

2019-03-29

18.4Sum

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.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def fourSum(self, nums, target):
        results = []
        # NSum方法
        def findNsum(nums, target, N, result, results):
            # 对N进行判断，能否进行NSum操作
            if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination
                return
            # N为2时前后两端循环求
            if N == 2: # two pointers solve sorted 2-sum problem
                l,r = 0,len(nums)-1
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            # N>2
            else: # recursively reduce N
                # 第i个数拿出来，将剩余的数进行(N-1)Sum,N>3时迭代循环
                for i in range(len(nums)-N+1):
                    if i == 0 or (i > 0 and nums[i-1] != nums[i]):
                        findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)


        findNsum(sorted(nums), target, 4, [], results)
        return results
-->