# 15. 三数之和

## 题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

> 例如, 给定数组 nums = \[-1, 0, 1, 2, -1, -4]，
>
> 满足要求的三元组集合为： \[ \[-1, 0, 1], \[-1, -1, 2] ]

## 解题

我们选择一个人做C位，既然是C位，那么就需要左右各有一个人。先选择队伍最左边（最小值）和队伍最右边（最大值）两个人，加上你，算一下总和。如果大于 0，说明实力太强了，就把就把右侧的人选调左一位，反之，则调整左边的人选，增强一下实力。当某边选到紧挨着你的人的时候，就意味着组队结束，以你为 C位的所有可能都已经尝试完毕了。

```javascript
var threeSum = function (nums) {
    let res = []
    let length = nums.length;
    nums.sort((a, b) => a - b) // 先排个队，最左边是最弱（小）的，最右边是最强(大)的
    if (nums[0] <= 0 && nums[length - 1] >= 0) { // 优化1: 整个数组同符号，则无解
      for (let i = 0; i < length - 2;) {
        if (nums[i] > 0) break; // 优化2: 最左值为正数则一定无解
        let first = i + 1
        let last = length - 1
        do {
          if (first >= last || nums[i] * nums[last] > 0) break // 两人选相遇，或者三人同符号，则退出
          let result = nums[i] + nums[first] + nums[last]
          if (result === 0) { // 如果可以组队
            res.push([nums[i], nums[first], nums[last]])
          }
          if (result <= 0 ) { // 实力太弱，把菜鸟那边右移一位
            while (first < last && nums[first] === nums[++first]){} // 如果相等就跳过
          } else { // 实力太强，把大神那边右移一位
            while (first < last && nums[last] === nums[--last]) {}
          }
        } while (first < last)
        while (nums[i] === nums[++i]) {}
      }
    }
    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://mm.ricky.moe/algorithm/algorithm-and-data-structure/leetcode/15.-san-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.