# 0015. 3Sums
###### tags: `Leetcode` `双指针`
Link：https://leetcode.com/problems/3sum/
# 思路
题目中要求找到所有**不重复**且和为 0 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下，数组中的元素全部为 0，即[0, 0, 0, 0, 0, ..., 0, 0, 0], 任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到 O(N^3) 个满足题目要求的三元组（其中 N 是数组的长度）时间复杂度至少为 O(N^3)。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题。

「不重复」的本质是什么？**我们保持三重循环的大框架不变**，只需要保证：

**第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；**
**第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。**

要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。

同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。举个例子，如果排完序的数组为
[0, 1, 2, 2, 2, 3]
^ ^ ^
我们使用三重循环枚举到的第一个三元组为(0,1,2)，如果第三重循环继续枚举下一个元素，那么仍然是三元组 (0,1,2)，产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素，即数组中的最后一个元素 3，枚举三元组 (0,1,3)。

这种方法的时间复杂度仍然为 O(N^3)，毕竟我们还是没有跳出三重循环的大框架。然而它是很容易继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b'时，由于 b'>b，那么满足 a+b'+c'=0 的 c'一定有 c'<c，即 c'在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即**第二重循环和第三重循环实际上是并列的关系**。

有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针。
# Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        if(nums.empty() || nums.size() <= 2){
            return result;   
        }
        for(int first = 0; first < nums.size()-1; first++){
            if(first>0 && nums[first]==nums[first-1]){
                continue;
            }
            int third = nums.size()-1;
            for(int second = first+1; second < nums.size();second++){
                if(second>first+1 && nums[second]==nums[second-1]){
                    continue;
                }
                while(second<third && nums[first]+nums[second]+nums[third]>0){
                    third--;
                }
                if(second==third){
                    break;
                }
                if(nums[first]+nums[second]+nums[third]==0){
                    vector<int> temp = {nums[first],nums[second],nums[third]};
                    result.push_back(temp);
                }
                
            }
        }
        return result;
    }
};

# Error
1. Line 1034: Char 9: runtime error: reference binding to null pointer of type 'int' (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:9
这里是因为没有考虑到输入可能是空的或者少于两个的情况，因此第一个回圈first = 0时，nums[first]可能根本没有值，因此才会有error
解决方法：

if(nums.empty() || nums.size() <= 2){
    return result;
}

2.见鬼了一样的error message
其实是因为vector的非法访问，例如vector size是10，访问到了第11个位置
这是因为原本第一个回圈我写的是```for(int first = 0; nums[first]<=0; first++)```因为如果first的位置对应的值是三个数里面最小的，如果nums[first]>0，就可以停掉。（其实这种情况考虑或不考虑都不会影响时间）但没有考虑到可能输入的vector里面的每个值都是小于0的。因此将其改成```for(int first = 0; first < nums.size()-1; first++)```