对于这么一个题目我们该如何入手呢？
很多人的第一感觉就是随机选择三个数就是写一个三层循环，然后按顺序随机选择三个数求和看是否等于0就行了，但是三层循环的方法在这道题里是行不通的，这里虽然没有写出时间复杂度的要求，但是O(N^3)是跑不过这道题的，这道题的时间复杂度要求是O(N^2)。
那么要在O(N^2)内写出这道题，那就最多只能写两层循环。
要通过两层循环选三个数，那么只能是一层循环选一个数，另一层循环同时选两个数。
具体思路：先把数组按升序的方式排好；外层循环按顺序先选定第一个数，如果这个数大于0，那么外循环就结束了，因为数组是升序的，当三个数中的第一个数都大于0，那么加上后面的数之后不可能等于0的；如果第一个数小于等于0，然后在内循环里面定义left和right下标，通过左右下标查找两个和为0的数，则这两个数和外循环选到的第一个数就组成了三元组，但是题目要求不能有重复的三元组，所以需要额外开一个set存储这些三元组。
下面是一个参考代码：时间复杂度为O(N^2)，空间复杂度为O(N^2)，思路非常的清晰，已配上非常详细的注释，相信大家都能看懂这个简单的代码的。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> vv;//存储返回的三元组 if (nums.size() < 3)//数组元素不足三个就直接返回了 { return vv; } sort(nums.begin(), nums.end());//对数组进行排序 set<vector<int>> set;//对三元组进行排序和去重(set的性质) int i = 0; for (i = 0; i < nums.size() - 2; i++)//外循环选的是第一个数，所以最多选到倒数第三个数 { //确定第一个数 int tmp = nums[i]; //如果tmp>0，数组升序，后面不可能找到<0的数，break； if (tmp > 0) { break; } //由于三元组内容是不重复的，所以在选择第一个数的时候数组中的重复元素可以跳过 if (i > 0 && nums[i] == nums[i - 1]) { continue; } //内循环找两个和为0的数 int begin = i + 1; int end = nums.size() - 1; //begin和end大小不能交叉 while (begin < end) { //i位置的数已经被第一个数选择了，同一个数不能同时选择两次，需跳过 if (begin == i) { begin++; //begin==end，说明中间无元素可选了 //break if (begin == end) { break; } } //i位置的数已经被第一个数选择了，同一个数不能同时选择两次，需跳过 if (end == i) { end--; //begin==end说明中间无元素可选了 //break if (begin == end) { break; } } //如果三个数相加<0,说明begin选小了(数组是升序的)，begin++，end位置已经是最大的值 //了，不能变 if (tmp + nums[begin] + nums[end] < 0) { begin++; } //如果三个数相加>0,说明end选大了，end--，begin位置已经是最小的值 //了，不能变 else if (tmp + nums[begin] + nums[end] > 0) { end--; } //三数相加等于0，说明这是一个三元组，插入到insert中 else { //找到的begin位置的元素的下一个元素还可能和begin位置的值相同， //这时可以去除重复的元素，减少运行的次数 while (begin + 1 < end && nums[begin] == nums[begin + 1]) { begin++; } //找到的end位置的元素的上一个元素还可能和end位置的值相同， //这时可以去除重复的元素，减少运行的次数 while (begin < end - 1 && nums[end] == nums[end - 1]) { end--; } //用这三个数构成一个三元组vector，这时已经是按顺序排好了 //直接插入到set就行 vector<int> v = { tmp,nums[begin],nums[end] }; set.insert(v); //改变坐标，继续寻找下一个三元组 begin++; end--; } } } //最后把set里存的三元组插入到vv里返回即可 for (auto& e : set) { vv.push_back(e); } return vv; } };
