[Leetcode15]三数之和

个人向，仅作记录回顾

双指针

问题

给你一个包含 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  vector<vector<int>> threeSum(vector<int>& nums) {
    
        /* * 题目给了一个数组。要求枚举出所有三个数字相加等于零的组合。且组合不能重复。 * 直接用三重循环枚举的话。需要额外判断组合之间是否重复。 * 如果先对nums进行排序。要求枚举出来的三个数字有a<=b<=c。那么就可以避免重复。 */
        sort(nums.begin(), nums.end());

        /*获取nums大小。即将开始枚举。*/
        int size = nums.size();

        //存放结果
        vector<vector<int>> ans;

        for (int first = 0; first < size; first++) {
    //在first=n-1的时候。开不出第二个for循环。
            /*为了避免枚举出的组合的重复*/
            if (first > 0 && nums[first] == nums[first - 1])
                continue;
            /*目标是三个数字的和等于零。那么随着second这个下标越来越大。third越来越小。 * 开始双指针。先初始化third */
            int third = size - 1;
            for (int second = first + 1; second < size; second++) {
    
                /*还是为了避免枚举出的组合的重复*/
                if (second > first + 1 && nums[second] == nums[second - 1])
                    continue;
                /*还是先避免组合的重复*/
                while (third > second && third < size - 1 && nums[third] == nums[third + 1])
                    third--;
                /*不满足条件的话，继续左移third*/
                while (third > second && nums[third] + nums[second] > -nums[first])
                    third--;
                /*双指针重叠的时候。second指针继续右移的话。也不会再满足题意了 * 但是first还可以继续右移。 */
                if (third == second)
                    break;
                if (nums[third] + nums[second] == -nums[first])
                    /*初始化vector<int>的一种好用的方法{1,2,3}*/
                    ans.push_back({
     nums[first],nums[second],nums[third] });
                /*小于的情况不用考虑了。继续右移second就能解决*/
            }
        }
        return ans;
    }