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

ftggdnt

一、题目解读

力扣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)。关键在于利用有序数组的特性，通过首元素固定与双指针动态收缩区间，同时结合去重逻辑保证结果**性。适用于求解多元素和为定值的问题，是算法面试中的高频考点。

来源：力扣题解