# \[18]\[中等]\[双指针] 四数之和

## 题目描述

[18. 四数之和](https://leetcode-cn.com/problems/4sum/)

给定一个包含 n 个整数的数组 nums 和一个目标值 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]
]
```

## 解题思路

对于$$N \ge 3$$的$$N$$数之和题目, 思路都是**先排序**, 然后固定前面若干位的数, 剩余两个位置, 由于是有序数组, 可以参考[\[167\]\[简单\]\[双指针\]\[二分\] 两数之和 II - 输入有序数组](broken://pages/-MDAko765bqUy8DHlBtp), 使用双指针求解.

细节上注意由于答案中不包含重复的四元组, 可以使用`set`去重, 也可以在循环时, 对连续的重复数字只考虑最前面的情况, 后续重复位置得到的结果都是重复的, 可以跳过这些位置.

```python
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if n < 4:
            return []

        nums.sort()
        res = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue

                diff = target - nums[i] - nums[j]
                left, right = j + 1, n - 1
                while left < right:
                    t = nums[left] + nums[right]
                    if t == diff:
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        right -= 1
                        left += 1
                    elif t > diff:
                        right -= 1
                    else:
                        left += 1
        return res
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/shu-zu/18-si-shu-zhi-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.