力扣15题三数之和解法（C++双指针算法详解）

fiwhgikbl

一、题目解读

力扣15题（三数之和）要求在一个包含n个整数的数组中，找出所有三个数之和为0的组合，且每个组合的元素不能重复。题目考察数组遍历、排序算法与双指针技巧的结合，是经典的多指针问题，对时间复杂度优化有较高要求。

二、解题思路

采用“双指针”策略：首先对原数组排序，然后固定**个数，通过左右指针在剩余区间内寻找和为目标的数对。核心逻辑在于利用排序后的有序性，通过双指针移动减少无效遍历，并跳过重复元素避免结果重复。

三、解题步骤

1. 排序预处理：对输入数组进行升序排序，为后续双指针操作奠定基础。

2. 外层循环固定首元素：遍历数组，每次固定**个数（需跳过重复值）。

3. 双指针搜索：

○ 初始化左指针为i+1，右指针为数组末尾；

○ 计算当前三数之和，若为0则记录结果，并移动左右指针时需跳过重复元素；

○ 若和小于0，左指针右移扩大和值；若和大于0，右指针左移缩小和值。

4. 循环终止条件：确保左指针始终在右指针左侧，避免重复计算。

四、代码与注释

1. class Solution {
   
2. public:
   
3.     vector<vector<int>> threeSum(vector<int>& nums) {
   
4.         vector<vector<int>> result;
   
5.         int n = nums.size();
   
6.         
   
7.         // 1. 排序预处理
   
8.         sort(nums.begin(), nums.end());
   
9.         
   
10.         // 2. 固定首元素遍历
    
11.         for (int i = 0; i < n - 2; ++i) {
    
12.             // 跳过重复首元素（优化）
    
13.             if (i > 0 && nums[i] == nums[i - 1]) continue;
    
14.             
    
15.             int left = i + 1;     // 左指针
    
16.             int right = n - 1;    // 右指针
    
17.             int target = -nums[i]; // 目标值（三数和为0，即其余两数和为-target）
    
18.             
    
19.             // 3. 双指针搜索
    
20.             while (left < right) {
    
21.                 int sum = nums[left] + nums[right];
    
22.                 if (sum == target) {
    
23.                     // 找到有效组合
    
24.                     result.push_back({nums[i], nums[left], nums[right]});
    
25.                     // 跳过重复的left和right元素
    
26.                     while (left < right && nums[left] == nums[left + 1]) ++left;
    
27.                     while (left < right && nums[right] == nums[right - 1]) --right;
    
28.                     ++left;  // 移动指针
    
29.                     --right;
    
30.                 } else if (sum < target) {
    
31.                     ++left;   // 和太小，右移左指针
    
32.                 } else {
    
33.                     --right;  // 和太大，左移右指针
    
34.                 }
    
35.             }
    
36.         }
    
37.         return result;
    
38.     }
    
39. };

复制代码

注释说明：代码中通过排序降低复杂度，双指针动态调整搜索范围，并利用跳过重复元素避免冗余计算，确保结果正确且不重复。

五、总结

该解法通过排序和双指针技术将时间复杂度优化至O(n^2)，空间复杂度O(1)。关键在于利用有序数组的特性，通过首元素固定与双指针动态收缩区间，同时结合去重逻辑保证结果**性。适用于求解多元素和为定值的问题，是算法面试中的高频考点。

来源：力扣题解