給定一個包含 n 個整數(shù)的數(shù)組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復的四元組。

注意：

答案中不可以包含重復的四元組。

示例：

給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

滿足要求的四元組集合為：

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

思路--雙指針

首先判斷如果數(shù)組為空，或者數(shù)字長度小于4，則直接返回空數(shù)組。
接著對數(shù)組進行排序。
與三數(shù)之和類似，需要多加一層循環(huán)
遍歷數(shù)組：
首先，首先固定第一個元素
如果當前的數(shù)字和前一個數(shù)字相同，那么對于重復元素：直接跳過本次循環(huán)，避免出現(xiàn)重復解
接著，固定第二個元素，
同樣，如果當前的數(shù)字和前一個數(shù)字相同，那么對于重復元素：直接跳過本次循環(huán)，避免出現(xiàn)重復解
令 c = b + 1，d = len(nums) - 1，當c< d，執(zhí)行循環(huán)：
若nums[a] + nums[b] + nums[c] + nums[d] > target，說明總和太大，d左移
若nums[a] + nums[b] + nums[c] + nums[d] < target，說明總和太小，c 右移
若nums[a] + nums[b] + nums[c] + nums[d] == target，則將當前的元素添加到結(jié)果集中，同時執(zhí)行循環(huán)，判斷左界和右界是否和下一位置重復，去除重復解，并同時將 c，d移到下一位置，尋找新的解

python3解法

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if not nums or len(nums) < 4:
            return  []
        nums.sort()
        ans = []
        # 首先固定第一個元素，注意范圍邊界
        for a in range(len(nums) - 3):
            # 確保第一個元素真的變了
            if a > 0 and nums[a] == nums[a - 1]: continue
            # 接著固定第二個元素，每次都是第一個元素的下一個元素
            for b in range(a + 1, len(nums) - 2):
                # 確保第二個元素真的變了
                if b > a + 1 and nums[b] == nums[b - 1]: continue
                # 雙指針確定地3,4個元素，第三個元素是第二個元素的下一個元素，第的哥元素始終從最后一個元素開始遍歷
                c = b + 1
                d = len(nums) - 1
                while c < d:
                    if nums[a] + nums[b] + nums[c] + nums[d] > target:
                        d -= 1
                    elif nums[a] + nums[b] + nums[c] + nums[d] < target:
                        c += 1
                    else:
                        ans.append([nums[a], nums[b], nums[c], nums[d]])
                        # 右移指針，確保跳過重復元素
                        while c < d and nums[c] == nums[c + 1]:
                            c += 1
                        # 左移指針，確保跳過重復元素
                        while c < d and nums[d] == nums[d - 1]:
                            d -= 1
                        c += 1
                        d -= 1
        return ans

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/4sum
著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。