1.7 双指针专题：三数之和（medium）

1.题目链接

15. 三数之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/submissions/609626561/

2.题目描述

给你⼀个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满⾜ i != j、i != k 且 j != k ，同时还满⾜ nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

⽰例 1：

• 输⼊：nums = [-1,0,1,2,-1,-4]
• 输出：[[-1,-1,2],[-1,0,1]]

解释：

• nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
• nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
• nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意，输出的顺序和三元组的顺序并不重要。

⽰例 2：

• 输⼊：nums = [0,1,1]
• 输出：[]

解释：唯⼀可能的三元组和不为 0 。

⽰例 3：

• 输⼊：nums = [0,0,0]
• 输出：[[0,0,0]]

解释：唯⼀可能的三元组和为 0 。

提⽰：

3 <= nums.length <= 3000

-10^5 <= nums[i] <= 10^5

3.算法思路

3.1 暴力枚举法思路分析

暴力法通过三重循环枚举所有可能的三元组：

1. 三重循环遍历：分别用 i, j, k 遍历数组，满足 i < j < k。

2. 条件检查：若 nums[i] + nums[j] + nums[k] == 0，记录该组合。

3. 去重处理：需额外使用哈希表或排序去重，时间复杂度进一步增加。

时间复杂度：O(n³)，效率极低，无法处理较大规模数据。

3.2 双指针算法思路分析

该问题要求找到所有不重复的三元组，使得它们的和为0。以下是双指针解法的核心步骤：

1. 排序预处理
   首先对数组排序，使相同元素相邻，便于后续去重操作，并为双指针法创造有序条件。

2. 固定第一个数
   遍历数组，将当前元素 nums[i] 作为三元组的第一个数。若 nums[i] > 0，由于数组已排序，后续元素均为正数，三数之和必大于0，直接终止循环。

3. 双指针搜索剩余两数
   对于固定的 nums[i]，问题转化为在右侧子数组中寻找两数之和为 -nums[i]。设置双指针：

   • left = i + 1（子数组左端）

   • right = nums.size() - 1（子数组右端）

   通过调整双指针的位置：

   • 若 nums[left] + nums[right] < target，左指针右移增大和。

   • 若 nums[left] + nums[right] > target，右指针左移减小和。

   • 若等于目标值，记录三元组，并跳过重复的 left 和 right。

4. 去重处理

   • 外层去重：当 nums[i] == nums[i-1] 时，跳过当前 i，避免重复作为第一个数。

   • 内层去重：找到有效三元组后，跳过所有与 nums[left] 和 nums[right] 相同的元素。

时间复杂度：O(n²)，排序 O(n log n)，双指针搜索 O(n²)。

3.3 双指针与暴力枚举法对比

对比项	双指针法	暴力枚举法
时间复杂度	O(n²)	O(n³)
空间复杂度	O(1) 或 O(n²)（取决于结果数量）	O(1) 或 O(n³)（去重存储开销）
前提条件	数组必须有序	无要求，但去重复杂
去重策略	利用有序性直接跳过重复元素	需额外数据结构或排序后处理
适用场景	大规模数据（1e4以上）	极小规模数据（n < 100）
代码复杂度	中等（需处理指针移动和去重）	简单（但效率极低）

4.代码实现

#include <vector>
class Solution 
{
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1.排序sort(nums.begin(),nums.end());// 2.利用双指针思想解决问题int length = nums.size();vector<vector<int>> arr;for(int i = 0; i< length; ) // 固定第一个数{if(nums[i] > 0) break; // 提前终止int left = i + 1, right = length - 1, target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum < target) left++;else if(sum > target) right--;else{arr.push_back({nums[i],nums[left],nums[right]});left++,right--;// 跳过重复的left和rightwhile(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}} // 跳过重复的ii++;while(i < length && nums[i] == nums[i - 1]) i++;}return arr;}
};