题目链接：https://leetcode.cn/problems/3sum/
还是只会暴力搜索，提交之后就报运行超时（通过用例数：315/318）。。。。看到题目就知道有更好的算法，但是你没做过就是想不到。。。
等我研究官方题解再更新吧。。。官方题解已更新，参考了评论区的改进版本，感觉更容易理解～
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
class Solution { public: /* 暴力搜索法 vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { for (int k = j + 1; k < nums.size(); k++) { if (nums[i] + nums[j] + nums[k] == 0) { vector<int> tmp{nums[i], nums[j], nums[k]}; sort(tmp.begin(), tmp.end()); int n = 0; for (; n < ret.size(); n++) { if (tmp == ret[n]) { break; } } if (n == ret.size()) { ret.push_back(tmp); } } } } } return ret; } */ vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); // 先排序，后面好遍历 int size = nums.size(); vector<vector<int>> ret; if (size < 3) { // 数组元素少于3 return ret; } for (int i = 0; i < size; i++) { // 遍历开始 if (i > 0 && nums[i] == nums[i-1]) { // 跟前一个元素相同，跳过 continue; } if (nums[i] > 0) { // 最小数字已经大于0，因为是排序好的，那后面的肯定也大于0，就没有必要继续遍历了 return ret; } int left = i + 1; // 双指针的左侧位置 int right = size - 1; // 双指针的右侧位置 while (left < right) { // 开始双指针相对移动 if (nums[i] + nums[left] + nums[right] < 0) { // 和<0，意味着要增大其中一个数字，所以移动左侧指针（向右） left++; } else if (nums[i] + nums[left] + nums[right] > 0) { // 和>0，则要减小一个数字，所以移动右侧指针（向左） right--; } else { // 找到和=0的三元组 ret.push_back({nums[i], nums[left], nums[right]}); left++; // 继续下一轮 right--; // 继续 // 这里是关键点，要跳过相同的三元组，我之前写的是跟left+1比较，所以一直解答错误， // 如果是left+1，因为上面已经left++了，所以就变成了下一个和下下一个比较，而不是当前和下一个比较了，下面的right也是一样， // 除非把left++和right--移到这两次遍历的下面，那样就可以用left和left+1比较了。 while (left < right && nums[left] == nums[left-1]) left++; while (left < right && nums[right] == nums[right+1]) right--; } } } return ret; } }; |
