双指针--双数之和
题目解析
给定一个整数数组nums，要求找出所有不重复的三元组[nums[i], nums[j], nums[k]]，满足：
- 索引互不相同：
i != j、i != k、j != k - 三数之和为 0：
nums[i] + nums[j] + nums[k] = 0 - 结果中不能包含重复的三元组
核心思路
这道题的难点在于去重和时间复杂度优化，直接暴力枚举的时间复杂度是 \(O(n^3)\)，会超时。我们可以用排序 + 双指针的方法，将时间复杂度优化到 \(O(n^2)\)。
算法步骤
- 排序预处理先对数组进行排序，这样可以利用有序性进行双指针的移动和去重操作。
- 固定第一个数遍历数组，将当前元素作为三元组的第一个数
nums[i]。- 如果当前数和前一个数相同，直接跳过（去重）。
- 如果当前数大于 0，因为数组是有序的，后面的数也都是正数，三数之和不可能为 0，直接终止循环。
- 双指针寻找另外两个数用左指针
left = i + 1和右指针right = nums.size() - 1来寻找另外两个数：- 计算三数之和
sum = nums[i] + nums[left] + nums[right] - 如果
sum < 0：说明需要更大的数，左指针右移 - 如果
sum > 0：说明需要更小的数，右指针左移 - 如果
sum = 0：记录该三元组，并移动左右指针跳过重复值
- 计算三数之和
完整代码
cpp
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; int n = nums.size(); if (n < 3) return res; // 数组长度不足3，直接返回空 sort(nums.begin(), nums.end()); for (int i = 0; i < n - 2; ++i) { // 去重：跳过与前一个元素相同的情况 if (i > 0 && nums[i] == nums[i-1]) continue; // 剪枝：如果当前数已经大于0，后面不可能组成和为0的三元组 if (nums[i] > 0) break; int left = i + 1; int right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum < 0) { left++; } else if (sum > 0) { right--; } else { // 找到一个符合条件的三元组 res.push_back({nums[i], nums[left], nums[right]}); // 跳过左指针重复值 while (left < right && nums[left] == nums[left+1]) left++; // 跳过右指针重复值 while (left < right && nums[right] == nums[right-1]) right--; // 移动指针继续寻找 left++; right--; } } } return res; } };关键优化点
- 排序去重：排序后，相同的元素会相邻，我们可以很方便地跳过重复值。
- 剪枝操作：当固定的第一个数大于 0 时，直接终止循环，因为后面的数都是正数，不可能组成和为 0 的三元组。
- 双指针移动：找到符合条件的三元组后，需要同时移动左右指针，并跳过重复值，避免生成重复的三元组。
复杂度分析
- 时间复杂度：\(O(n^2)\)，其中排序的时间复杂度是 \(O(n \log n)\)，双指针遍历的时间复杂度是 \(O(n^2)\)。
- 空间复杂度：\(O(\log n)\)（排序的栈空间）或 \(O(n)\)（如果使用了额外的数组存储结果）。