> For the complete documentation index, see [llms.txt](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/linear-list/array/3sum.md).

# 3Sum

medium 原题链接：https\://leetcode.com/problems/find-minimum-in-rotated-sorted-array/submissions/

## 3Sum

原题链接：<https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/submissions/>

### 描述

> Given an array `nums` of *n* integers, are there elements *a*, *b*, *c* in `nums` such that *a* + *b* + *c* = 0? Find all unique triplets in the array which gives the sum of zero.
>
> Notice that the solution set must not contain duplicate triplets.

### 例子

> Input: nums = \[-1,0,1,2,-1,-4]&#x20;
>
> Output: \[\[-1,-1,2],\[-1,0,1]]

### 约束条件

* `0 <= nums.length <= 3000`
* `-105 <= nums[i] <= 105`

### 解法一

```cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size()<3) return res;
        sort(nums.begin(),nums.end());
        int len = nums.size();
        for(int i=0; i< len-2; i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]>0) break;
            if(nums[i]+nums[len-2]+nums[len-1]<0) continue;
            int j=i+1, k=len-1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum > 0) --k;
                else if(sum < 0) ++j;
                else{
                    res.push_back({nums[i],nums[j],nums[k]});
                    do{++j;}while(nums[j] == nums[j-1] && j<k);
                    do{--k;}while(nums[k] == nums[k+1] && j<k);
                }
            }
                
        }
        return res;
        
    }
};
```

### 解法二

```cpp
```