18 四数之和.md

18、四数之和

题目：

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

方法一：

这道题与三数之和类似。

（1）三数之和固定一个指针，让它每次循环。其他两个指针，做双指针碰撞。

（2）四数之和固定两个指针，外层双循环。其他两个指针，做双指针碰撞。

以下方法的难点在于去重。所谓去重，是指index的值nums[index]不能与nums[index-1]相同。如果相同，一定会出现重复的四个数。

去重有两种方法：

（1）去掉第一个值

（2）去掉第二个值

这里（left和right）先变化index，然后比较前一个值，这属于（1），可以防止指针越界。

如果当前值，与后面依次的三个值之和（nums[index1]+nums[index1+1]+nums[index1+2]+nums[index1+3]）已经大于target了，那就说明后面的所有组合都大于target，循环break。

如果当前值，与最后的三个值之和（nums[index1]+nums[len(nums)-1]+nums[len(nums)-2]+nums[len(nums)-3]）小于target，那说明当前的指针太小，需要往后移，这一轮循环略过continue。

"""
双循环，双指针碰撞
index1:[0，len-1-3]
index2:[index1+1, len-1-2]
left=index2+1
right=len-1
"""

nums=[0,0,0,0]

def fourSum(nums, target):
    if len(nums) < 4:
        return []
    nums.sort()
    result = []
    for index1 in range(len(nums) - 3):
        #index1去重
        if index1>0 and nums[index1]==nums[index1-1]: continue
        
        if nums[index1]+nums[index1+1]+nums[index1+2]+nums[index1+3]>target: break
        if nums[index1]+nums[len(nums)-1]+nums[len(nums)-2]+nums[len(nums)-3]<target: 				continue
            
        for index2 in range(index1 + 1, len(nums) - 2):
            # index2去重
            if index2>index1+1 and nums[index2] == nums[index2 - 1]: continue
            
            if nums[index1]+nums[index2]+nums[index2+1]+nums[index2+2]>target: break
            if nums[index1]+nums[index2]+nums[len(nums)-1]+nums[len(nums)-2]<target: 					continue
                    
            left = index2 + 1
            right = len(nums) - 1
            while (left < right):
                sum = nums[index1] + nums[index2] + nums[left] + nums[right]
                if sum == target:
                    temp = []
                    temp.append(nums[index1])
                    temp.append(nums[index2])
                    temp.append(nums[left])
                    temp.append(nums[right])
                    result.append(temp)
                    left += 1
                    while(left<right and nums[left] == nums[left - 1]): left += 1
                    right -= 1
                    while(left<right and nums[right] == nums[right + 1]): right -= 1
                elif sum < target:
                    left += 1
                    #left去重
                    while left < right and nums[left] == nums[left - 1]: left += 1
                elif sum > target:
                    right -= 1
                    #right去重
                    while left < right and nums[right] == nums[right + 1]: right -= 1
    return result

方法二：

递归算法。算出N数之和。

递归构造一棵树，这个树的路径包含了所有的可能性，将不符合条件的路径剪枝。

def fourSum2(nums, target):

    def nSum(L, R, target, N, result, results):

        if R-L+1<N or target<nums[L]*N or target>nums[R]*N or N<2:
            return
        if N == 2:
            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
                    R -= 1
                    while L<R and nums[R]==nums[R+1]: R -= 1
                elif s<target:
                    L += 1
                    while L<R and nums[L] == nums[L - 1]: L += 1
                else:
                    R -= 1
                    while L<R and nums[R] == nums[R + 1]: R -= 1
        else:
            for i in range(L, R+1):
                if L==i or (i>L and nums[i]!=nums[i-1]):
                    nSum(i+1, R, target-nums[i], N-1, result+[nums[i]], results)

        L = 0
        R = len(nums)-1
        N=4
        result=[]
        results=[]
        nums.sort()

        nSum(L, R, target, N, result, results)
        return results

剪枝，剪枝，剪枝。。。

这次的坑是s = nums[L]+nums[R]，如果每次比较target和nums[L]+nums[R]的关系，那么随着L和R的改变，会造成nums[L]+nums[R]在同一轮while下不断变化。