题目分析

题目链接：

搜索问题的思路

这又是一个搜索的问题（从数组中搜索满足条件的三元组），我在中总结过搜索问题的一般解法：

搜索最佳结果的一个一般思想：先想象这个最佳结果必定具有什么样的特征，然后我们通过这些特征来查找，不断找出很多“候选最佳结果”，最后从这些候选结果中选拔出最佳的结果。

那么，和为0的三元组满足什么条件呢？首先，不妨让三元组的3个元素从小到大排列，因此第一个元素就是最小的元素。如果第一个元素为left，则另外两个元素之和为-left，这是一个充要条件。

因此，搜索的思路就出来了：依次对每个数字都假定它是left，然后从大于等于left的数字中找到和为-left的两个数字，如果找到了，则这三个数字可以组成和为0的三元组。

为什么只需要从大于等于left的数字中找？因为我们已经假设了三元组按照从小到达排列。这个假设不妨碍我们找到所有符合条件的三元组，而且大大降低了搜索的时间。

算法步骤

1. 首先对输入数组vector<int>& nums进行排序。这不但有利于我们依次对每个数字都假定它是left，而且有利于我们从大于等于left的数字中找到和为-left的两个数字。
2. 从小到大，依次假设每一个数字为left。
3. 从数组的left_index+1～size()-1下标范围内，找到2个和为-left的数字。如果找到了就将三元组放入结果集合vector<vector<int>> res中，然后在这个下标范围继续搜索。
4. 数组的left_index+1～size()-1下标范围搜索完毕后，回到步骤2，假设下一个数字为left。直到所有数字都已经被假设过为left。
5. 返回结果集合res。

代码实现

class Solution {public:    vector
    
     
      > threeSum(vector
      
       & nums) {        vector
       
        
         > res;        int length = nums.size();                std::sort(nums.begin(), nums.end());                for (int left = 0; left < length; left++) {            int shouldHaveSum = -1*nums[left];            int i = left+1, j = length-1;            while (i < j) {                int sum = nums[i]+nums[j];                if (sum == shouldHaveSum) {                    vector
         
           triplet(3); triplet[0] = nums[left]; triplet[1] = nums[i]; triplet[2] = nums[j]; res.push_back(triplet); // 为了不重复输出三元组，我们跳过已经在上一个三元组中的数字 while (i < j && nums[i] == triplet[1]) ++i; while (i < j && nums[j] == triplet[2]) --j; } else if (sum < shouldHaveSum) { // sum太小，通过增加第二个数字让sum大一些 ++i; } else if (sum > shouldHaveSum) { // sum太大，通过减小第三个数字让sum小一些 --j; } } // 为了不重复输出三元组，我们不多次假设同一个数字为left while (left+1 < length && nums[left+1] == nums[left]) ++left; } return res; }};
         
        
       
      
     
    

时间复杂度

最外层循环(依次假设每个数字为left)做length次。内层循环相当于遍历那些在left右边的所有数字，时间复杂度为O(length)。