C++编程-leetcode-三数之和-组合数求解

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

思路：
这道题属于组合数求解，通常求组合数我们会用回溯算法，但是本题带有条件性，也就是三数之和为0，那或许我们可以增加某些条件，使回溯算法可以解决这道题，但是却难以真正抛开许多冗余的部分，导致时间过长。一般情况下，只要时间允许，我们可以使用多层循环来解决每一道需要遍历的问题，但偏偏时间就是不允许，因为这方面会增加很多的冗余成分，导致时间过长，而大多数算法则是根据实际问题逐渐将多层循环的冗余成分剔除，达到优化。也就是说，一般最坏的情况就是多层循环，多次遍历了，基于此我们可以再做优化。
也就是说，如果是解决2层3层或者4层循环的题目，只要能做优化，那么是可以使用多层循环，但如果是解决较高或者不明的层数，那么就需要使用回溯算法。
由于只有三个数，这就给我们提示，我们是可以使用多层循环的，在这种情况下，多层循环一般复杂度都要高于O(n^2) ，而排序的复杂度最高一般O(n^2) ，那么我们也就不用吝啬不用冒泡排序或者快速排序了。先用快速排序把数组nums排好序。
三个数，我们每次固定一个数，假设我们固定第一个数i，那么第二个数j=i+1，而第三个数则是t=length-1.也就是说固定一个数后，在剩下的n-1个数中，我们从两端向中间靠，因为已经排好序，那么右边t肯定高于左边j。当三个数加起来大于0，说明需要减少，那么只能加，t只能减，所以t–。当低于0，那么j++。这种情况就把三层循环的复杂度降低至O(n^2)了。

代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int length = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for(int i=0;i<length;i++)
        {
            if(i>0 &&nums[i]==nums[i-1])
            {
                continue;
            }
            int j,t;
            int target=0-nums[i];
            j=i+1;
            t=length-1;
            while(j<t)
            {
                int now=nums[j]+nums[t];
                if(now==target)
                {
                    ans.push_back({nums[i],nums[j],nums[t]});
                    j++;
                    t--;
                    while(j<t&&nums[j]==nums[j-1])
                    {
                        j++;
                    }
                    while(j<t&& nums[t]==nums[t+1])
                    {
                        t--;
                    }
                }
                else
                {
                    if(now>target)
                    {
                        t--;
                    }
                    else
                    {
                        j++;
                    }
                }

            }

        }
        return ans;

    }
};