三数之和

$images\cherry_red.png$ 1 Leetcodegaogaotwo

$images\cherry_blue.png$ 1.1 链表

$images\cherry_orange.png$ 1.1.1 分割链表

$images\cherry_orange.png$ 1.1.2 反转链表

$images\cherry_orange.png$ 1.1.3 快慢指针链表的中间节点

$images\cherry_orange.png$ 1.1.4 链表的倒数第k个节点

$images\cherry_orange.png$ 1.1.5 回文链表

$images\cherry_orange.png$ 1.1.6 链表的删除

$images\cherry_orange.png$ 1.1.7 链表反转2

$images\cherry_orange.png$ 1.1.8 链表的第一个相交节点

$images\cherry_blue.png$ 1.2 dfs

$images\cherry_orange.png$ 1.2.1 岛屿数量

$images\cherry_orange.png$ 1.2.2 机器人的运动范围

$images\cherry_orange.png$ 1.2.3 字符串的全排列(回溯算法)

$images\cherry_orange.png$ 1.2.4 判断一个数字是否可以表示成三的幂的和

$images\cherry_orange.png$ 1.2.5 不同路径III dfs+回溯

$images\cherry_orange.png$ 1.2.6 组合总和 dfs+回溯

$images\cherry_orange.png$ 1.2.7 子集 dfs or 状态枚举

$images\cherry_blue.png$ 1.3 bfs

$images\cherry_blue.png$ 1.4 双指针

$images\cherry_orange.png$ 1.4.1 奇数在前，偶数在后

$images\cherry_blue.png$ 1.5 二维矩阵的前缀和

$images\cherry_orange.png$ 1.5.1 1074. 元素和为目标值的子矩阵数量

$images\cherry_orange.png$ 1.5.2 304. 二维区域和检索 - 矩阵不可变

$images\cherry_blue.png$ 1.6 数组变化

$images\cherry_orange.png$ 1.6.1 大数加减法

$images\cherry_orange.png$ 1.6.2 717. 1 比特与 2 比特字符

$images\cherry_blue.png$ 1.7 排序算法

$images\cherry_orange.png$ 1.7.1 把数组排成最小的数

$images\cherry_orange.png$ 1.7.2 根据字符出现的次数频率进行排序

$images\cherry_orange.png$ 1.7.3 最大数

$images\cherry_orange.png$ 1.7.4 969. 煎饼排序

$images\cherry_blue.png$ 1.8 dp动态规划

$images\cherry_orange.png$ 1.8.1 斐波那契数列

$images\cherry_orange.png$ 1.8.2 俄罗斯套娃信封问题

$images\cherry_orange.png$ 1.8.3 分割回文串

$images\cherry_orange.png$ 1.8.4 01背包

$images\cherry_orange.png$ 1.8.5 打家劫舍II

$images\cherry_orange.png$ 1.8.6 青蛙过河

$images\cherry_orange.png$ 1.8.7 最长回文子串

$images\cherry_orange.png$ 1.8.8 目标和（01背包）

$images\cherry_orange.png$ 1.8.9 最大子序和

$images\cherry_blue.png$ 1.9 滑动窗口

$images\cherry_orange.png$ 1.9.1 绝对差不超过限制的最长连续子数组

$images\cherry_orange.png$ 1.9.2 三数之和

$images\cherry_blue.png$ 1.10 二叉树性质

$images\cherry_orange.png$ 1.10.1 二叉树的最小深度

$images\cherry_orange.png$ 1.10.2 二叉树的层次遍历

$images\cherry_orange.png$ 1.10.3 二叉树的镜像翻转

$images\cherry_orange.png$ 1.10.4 二叉树的最大深度

$images\cherry_orange.png$ 1.10.5 二叉搜索树节点最小距离

$images\cherry_orange.png$ 1.10.6 二叉树重构从小到达按照->right情况

$images\cherry_orange.png$ 1.10.7 二叉搜索数的范围和

$images\cherry_orange.png$ 1.10.8 N叉树的前序遍历

$images\cherry_blue.png$ 1.11 递归

$images\cherry_orange.png$ 1.11.1 1+2...+n

$images\cherry_blue.png$ 1.12 并查集

$images\cherry_orange.png$ 1.12.1 并查集连通分量

$images\cherry_orange.png$ 1.12.2 并查集城市连通

$images\cherry_blue.png$ 1.13 堆栈

$images\cherry_orange.png$ 1.13.1 通过队列来实现栈

$images\cherry_orange.png$ 1.13.2 下一个更大元素 II

$images\cherry_orange.png$ 1.13.3 删除字符串中的所有相邻重复项

$images\cherry_orange.png$ 1.13.4 基本计算机

$images\cherry_orange.png$ 1.13.5 计算机

$images\cherry_orange.png$ 1.13.6 逆波兰表达式

$images\cherry_orange.png$ 1.13.7 接雨水

$images\cherry_orange.png$ 1.13.8 柱状图中最大矩形面积

$images\cherry_orange.png$ 1.13.9 反转每对括号间的子串

$images\cherry_blue.png$ 1.14 队列（or 优先队列）

$images\cherry_orange.png$ 1.14.1 最大平均通过率

$images\cherry_orange.png$ 1.14.2 最大的团队表现值

$images\cherry_orange.png$ 1.14.3 找出第K大的异或坐标值

$images\cherry_orange.png$ 1.14.4 1.2滑动窗口的最大值

$images\cherry_orange.png$ 1.14.5 二叉搜索数的范围和

$images\cherry_orange.png$ 1.14.6 员工的重要性

$images\cherry_blue.png$ 1.15 Hash查询匹配

$images\cherry_orange.png$ 1.15.1 猜灯谜

$images\cherry_orange.png$ 1.15.2 720. 词典中最长的单词

$images\cherry_blue.png$ 1.16 前缀树

$images\cherry_orange.png$ 1.16.1 实现Trie(前缀树)

$images\cherry_orange.png$ 1.16.2 添加与搜索单词 - 数据结构设计

$images\cherry_blue.png$ 1.17 位运算

$images\cherry_orange.png$ 1.17.1 比特位计数

$images\cherry_orange.png$ 1.17.2 不用加减乘除做加法

$images\cherry_orange.png$ 1.17.3 可被 5 整除的二进制前缀

$images\cherry_orange.png$ 1.17.4 汉明距离总和

$images\cherry_blue.png$ 1.18 二分法

$images\cherry_orange.png$ 1.18.1 在D天内送达包裹的能力

$images\cherry_orange.png$ 1.18.2 第一个错误的版本

$images\cherry_blue.png$ 1.19 数据结构性质

$images\cherry_blue.png$ 1.20 回溯法思想

$images\cherry_blue.png$ 1.21 字符串处理(模拟)

$images\cherry_orange.png$ 1.21.1 Excel 表列序号进制转换

$images\cherry_orange.png$ 1.21.2 838.推多米诺

$images\cherry_blue.png$ 1.22 模拟

$images\cherry_blue.png$ 1.23 数学定理

$images\cherry_orange.png$ 1.23.1 1828. 统计一个圆中点的数目

15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

提示：

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

class Solution {
    vector<vector<int>>ans;
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.empty()||nums.size()<3){
            return ans;
        }
        int n = nums.size();
        sort(nums.begin(),nums.end());

        int i,j,k;

        for(i=n-1;i>=2&&nums[i]>=0;){
            int pos = nums[i];
            for(j=0,k=i-1;j<k;){
                int sum = nums[j] + nums[k];

                if(pos+sum>0){
                    k--;
                }
                else if(pos+sum<0){
                    j++;
                }
                else if(pos+sum==0){
                    vector<int>tep;
                    tep.push_back(nums[j]);
                    tep.push_back(nums[k]);
                    tep.push_back(nums[i]);
                    ans.push_back(tep);

                    do{
                        ++j;
                    }while(j<k&&nums[j-1]==nums[j]);

                    do{
                        --k;
                    }while(j<k&&nums[k+1]==nums[k]);
                }

            }
            do{
                --i;
            }while(i>=2&&nums[i+1]==nums[i]);
        }
        // ans.erase(unique(ans.begin(),ans.end()),ans.end());
        return ans;
    }
};