【力扣15】三数之和

15. 三数之和 - 力扣（LeetCode）

双指针算法核心：有序（有序了才能使用双指针）因此，先排序，且保证 i<j<k 的顺序；顺序确定，双指针才能有序移动，可以将原本 o(n2) 复杂度降未 o(n)

双指针：先想暴力做法，再看有没有单调性，有单调性就用双指针

有三个数，但只有双指针，所以先枚举一个数；后两个数按照双指针，根据题目给定限制条件，划定双指针活动范围。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res; //存储找到的三元组
        sort(nums.begin(), nums.end()); //排序，便于双指针
        for(int i = 0; i<nums.size(); i++){ //对i遍历
            if(i && nums[i]==nums[i-1]) 
                continue;// 跳过重复的元素
            //j、k双指针一前一后，且j始终在k前边；且控制左指针移动
            for(int j = i+1, k = nums.size()-1; j<k; j++){
                //j的位置、跳过重复元素
                if(j>i+1 && nums[j]==nums[j-1]) continue;
                //i、j已确定的情况下若和大于0，右指针该往前移动
                while(j<k-1 && nums[i]+nums[j]+nums[k-1]>=0) k--;
                //最终条件，将结果push入res中
                if(nums[i]+nums[j]+nums[k] == 0)
                    res.push_back({nums[i],nums[j],nums[k]});
            }
        }
        return res;
    }
};

二维数组，构成了一个矩阵，可以存储许多 多元组。每一个vector向量都可以存储一个数组，因此二维数组也可以存储三元组。