Leetcode-18.四数之和

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

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

代码：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        N = len(nums)
        nums_asc = sorted(nums)
        ans = []
        for a in range(0, N-3):
          	# 判断是否与前一个值相等
            if a>0 and nums_asc[a]==nums_asc[a-1]:
                continue
            for b in range(a+1, N-2):
                if b>a+1 and nums_asc[b]==nums_asc[b-1]:
                    continue
                c, d = b+1, N-1
                while(c<d):
                    val = nums_asc[a]+nums_asc[b]+nums_asc[c]+nums_asc[d]
                    if val > target:
                        d-=1
                    elif val < target:
                        c+=1
                    else:
                        ans.append([nums_asc[a], nums_asc[b], nums_asc[c], nums_asc[d]])
                        # 跳过相等的元素
                        while(c<d and nums_asc[c]==nums_asc[c+1]):
                            c+=1
                        while(c<d and nums_asc[d]==nums_asc[d-1]):
                            d-=1
                        c += 1
                        d -= 1
        return ans

双指针法，使用a, b, c, d四个变量，分别代表最小值，第二小值，剩余元素的首位和末尾。利用两个循环，外循环为a，内循环为b，循环体内通过判断四个值的和与target的大小关系，从而相应移动c, d。最后通过while循环过滤掉值相等的元素以防止得到重复的结果。