题目：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
解答：
代码一：
直接三个嵌套循环，然后移动两个index查找符合要求的结果，注意：题目中输出的内容是从小到大排序的，所以首先需要对输入数字进行排序
vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; if (nums.size() < 3) //元素至少3个 return result; //先排序 for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if (nums.at(i) > nums.at(j)) { int tmp = nums.at(i); nums.at(i) = nums.at(j); nums.at(j) = tmp; } } } auto isExist = [](vector<int>& vec,vector<vector<int>>& results)->bool{ for (auto val : results) { if (val.at(0) == vec.at(0) && val.at(1) == vec.at(1)) return true; } return false; }; int idx1 = 0, idx2 = 0; for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { int twoSum = nums.at(i) + nums.at(j); for (int k = j + 1; k < nums.size(); k++) { if ((twoSum + nums.at(k)) == 0) { vector<int> val = { nums.at(i), nums.at(j), nums.at(k) }; bool has = isExist(val, result); if (!has) { result.push_back(val); break;//找到一个后就break，因为第一个、第二个数字已经找了，往后再找第三个为重复的 } } } } } return result; }
提交后，超出时间限制。。。
上面的冒泡排序修改为<algorithm>中的sort：
sort(nums.begin(), nums.begin() + nums.size());
提交后仍是超出时间限制。问题应该是查找的那部分，时间复杂度为O(n^3)，修改后如下，时间复杂度为O(n^2)
vector<vector<int>> threeSum2(vector<int>& nums) { vector<vector<int>> result; if (nums.size() < 3) //元素至少3个 return result; //先排序 sort(nums.begin(), nums.begin() + nums.size()); if (nums.at(0) > 0) return result; //判断是否已经存在的lambda auto isExist = [](vector<int>& vec, vector<vector<int>>& results)->bool{ for (auto val : results) { if (val.at(0) == vec.at(0) && val.at(1) == vec.at(1)) return true; } return false; }; //1.排序后，如果前两个相加>0了，后面就不用找了 //2.对于第三个index，如果找到了就直接break了，因为前两个值一样，最终结果只有一条 int idx1 = 0, idx2 = 0; for (int i = 0; i < nums.size(); i++) { idx1 = i + 1; if (idx1 >= nums.size()) return result; if (nums.at(i) + nums.at(idx1) > 0)//前两个数大于零，不再找 break; idx2 = nums.size() - 1; while (idx1<nums.size() && idx2 > idx1) { if (nums.at(i) + nums.at(idx1) > 0)//前两个数大于零，不再找 return result; int val = nums.at(i) + nums.at(idx1) + nums.at(idx2); if (val == 0) { vector<int> val = { nums.at(i), nums.at(idx1), nums.at(idx2) }; bool has = isExist(val, result); if (!has) result.push_back(val); idx1++; idx2--; } else if (val > 0) idx2--; else if (val < 0) idx1++; } } return result; }
提交几次还是时间超出限制。。。应该是判断是否重复的问题，因为已经排序过了，再通过函数判断是否重复逻辑上存在重复，代码修改如下：
vector<vector<int>> threeSum2(vector<int>& nums) { vector<vector<int>> result; if (nums.size() < 3) //元素至少3个 return result; //先排序 sort(nums.begin(), nums.begin() + nums.size()); if (nums.at(0) > 0) return result; ////判断是否已经存在的lambda //auto isExist = [](vector<int>& vec, vector<vector<int>>& results)->bool{ // for (auto val : results) // { // if (val.at(0) == vec.at(0) && val.at(1) == vec.at(1)) // return true; // } // return false; //}; //1.排序后，如果前两个相加>0了，后面就不用找了 //2.对于第三个index，如果找到了就直接break了，因为前两个值一样，最终结果只有一条 int idx1 = 0, idx2 = 0; for (int i = 0; i < nums.size(); i++) { if (i > 0 && nums.at(i) == nums.at(i - 1))//跟上个元素相同的跳过，因为已经找了 continue; idx1 = i + 1; if (idx1 >= nums.size()) break; if (nums.at(i) + nums.at(idx1) > 0)//前两个数大于零，不再找 break; idx2 = nums.size() - 1; while (idx1<nums.size() && idx2 > idx1) { if (nums.at(i) + nums.at(idx1) > 0)//前两个数大于零，不再找 return result; if (idx1 > i+1 && nums.at(idx1) == nums.at(idx1 - 1))// { idx1++; continue; } int val = nums.at(i) + nums.at(idx1) + nums.at(idx2); if (val == 0) { vector<int> val = { nums.at(i), nums.at(idx1), nums.at(idx2) }; //bool has = isExist(val, result); //已经排序了，不用再判断重复 //if (!has) result.push_back(val); idx1++; idx2--; } else if (val > 0) idx2--; else if (val < 0) idx1++; } } return result; }
终于过了。。。
重点：双指针使用，以降低时间复杂度。