class Solution {

public:

    vector<vector<int>> threeSum(vector<int>& nums) {

        map<int, vector<size_t> > mp;

        map<string, bool> isExist;

        vector<vector<int>> res;

        for(size_t i = 0; i < nums.size(); i++){

            int num = nums[i];

            if(mp.find(num) != mp.end()){

                mp[num].push_back(i);

            }else{

                mp[num] = vector<size_t>{i};

            }

        }

        for(size_t i = 0; i < nums.size(); i++){

            for(size_t j = i + 1; j < nums.size(); j++){

                int num = 0 - nums[i] - nums[j];

                if(mp.find(num) != mp.end()){

                    for(size_t k : mp[num]){

                        if(k > j){

                            vector<int> ve{nums[i], nums[j], num};

                            sort(ve.begin(), ve.end());

                            string s = to_string(ve[0]) + to_string(ve[1]) + to_string(ve[2]);

                            if(!isExist[s]){

                                res.push_back(ve);

                                isExist[s] = true;

                            }

                        }

                    }

                }

            }

        }

        return res;

    }

};

class Solution {

public:

    vector<vector<int>> threeSum(vector<int>& nums) {

        int n = nums.size();

        sort(nums.begin(), nums.end());

        vector<vector<int>> ans;

        // 枚举 a

        for (int first = 0; first < n; ++first) {

            // 需要和上一次枚举的数不相同

            if (first > 0 && nums[first] == nums[first - 1]) {

                continue;

            }

            //c 对应的指针初始指向数组的最右端

            int third = n - 1;

            int target = -nums[first];

            // 枚举 b

            for (int second = first + 1; second < n; ++second) {

                // 需要和上一次枚举的数不相同

                if (second > first + 1 && nums[second] == nums[second - 1]) {

                    continue;

                }

                // 需要保证 b 的指针在 c 的指针的左侧

                while (second < third && nums[second] + nums[third] > target) {

                    --third;

                }

                // 如果指针重合，随着 b 后续的增加

                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环

                if (second == third) {

                    break;

                }

                if (nums[second] + nums[third] == target) {

                    ans.push_back({nums[first], nums[second], nums[third]});

                }

            }

        }

        return ans;

    }

};