【C++】优选算法必修篇之双指针实战：三数之和 & 四数之和

我不是呆头

发布于 2025-12-20 14:31:35

双指针应用场景

应用场景介绍----------<----------链接直达请点击

1. 三数之和

1.1 题目链接

题目链接直达请点击<----------

1.2 题目描述

1.3 题目示例

1.4 算法思路

三数之和问题的核心是在数组中找出所有不重复的三元组，使得它们的和等于零。双指针解法的关键在于先对数组进行排序，将无序问题转化为有序问题，从而能够利用双指针高效搜索。

首先将数组从小到大排序，排序后相同的数字会相邻排列，这为后续去重提供了便利。排序完成后，我们开始遍历数组，将当前遍历的元素作为三元组的第一个数。对于每一个固定的第一个数，我们将其相反数作为目标值，这样问题就转化为在剩余的子数组中寻找两个数，使它们的和等于这个目标值，也就是经典的两数之和问题。

在固定第一个数后，我们使用双指针技术在剩余区间内寻找另外两个数。左指针从第一个数后一位开始，右指针从数组末尾开始。计算当前双指针指向的两个数之和，与目标值比较。如果和小于目标值，说明需要更大的数，因此左指针右移；如果和大于目标值，说明需要更小的数，因此右指针左移；如果恰好等于目标值，就找到了一个有效的三元组。

找到解后的去重处理至关重要。在记录当前解后，我们需要同时移动左右指针，并且跳过所有重复的值，确保不会记录相同的三元组。在外层循环中，当移动到下一个第一个数时，如果发现与之前的数相同，也要跳过，避免以相同的数作为三元组的起点。此外，还有一个重要的剪枝优化：如果当前固定的第一个数已经大于零，由于数组是排序的，后面的数都更大，三数之和不可能为零，可以直接终止循环。

1.5 核心代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret; // 存储答案的容器

        // 先对数组进行排序，这是双指针解法的基础
        // 排序后可以方便地使用双指针，并且便于去重
        sort(nums.begin(), nums.end()); // 例如排序后：[-4, -1, -1, 0, 1, 2]

        int n = nums.size();
        
        // 遍历数组，固定第一个数
        for (int i = 0; i < n;) {
            // 将三数之和转化为两数之和问题：nums[left] + nums[right] = -nums[i]
            int left = i + 1, right = n - 1, target = -nums[i];
            
            // 剪枝优化：如果目标值小于0，说明nums[i] > 0
            // 由于数组已排序，后面的数都大于0，三数之和不可能为0，直接退出循环
            if (target < 0) break;
            
            // 双指针在 i+1 到 n-1 的区间内寻找两数之和等于target
            while (left < right) {
                int sum = nums[left] + nums[right];
                
                if (sum < target) {
                    left++; // 和太小，左指针右移
                } else if (sum > target) {
                    right--; // 和太大，右指针左移
                } else {
                    // 找到满足条件的三元组
                    ret.push_back({nums[i], nums[left], nums[right]});
                    
                    // 移动指针继续寻找其他可能的解
                    left++;
                    right--;
                    
                    // 去重：跳过左侧重复的元素
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    // 去重：跳过右侧重复的元素  
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            
            // 去重：跳过与当前nums[i]相同的元素，避免重复的三元组
            while (i + 1 < n && nums[i] == nums[i + 1]) i++;
            
            // 移动到下一个不同的数字
            i++;
        }
        
        return ret;
    }
};

1.6 示例测试（总代码）

2. 四数之和

2.1 题目链接

题目链接直达请点击<----------

2.2 题目描述

2.3 题目示例

2.4 算法思路

四数之和问题要求找出所有不重复的四元组，使得它们的和等于特定目标值。其双指针解法是三数之和的自然扩展，通过增加一层循环来固定更多的元素。

同样地，首先对数组进行排序，这是所有双指针技巧的基础。排序后我们使用两层循环来固定前两个数。外层循环固定第一个数，内层循环固定第二个数，第二个数从第一个数的下一位开始。这样我们就确定了四元组的前两个数。

然后计算剩余需要达到的目标值，即用总目标值减去前两个数的和。这里需要注意整数溢出问题，特别是当目标值很大而数组元素也很大的情况，因此通常需要使用长整型来存储中间计算结果。

在固定前两个数后，问题转化为在剩余子数组中寻找两个数，使它们的和等于计算得到的目标值。我们使用双指针技术，左指针从第二个数的下一位开始，右指针从数组末尾开始，相向移动寻找满足条件的数对。移动规则与三数之和相同：和太小则左指针右移，和太大则右指针左移，找到解后记录并继续搜索。

去重处理在四数之和中更为复杂，需要在三个位置进行去重：在外层循环跳过重复的第一个数，在内层循环跳过重复的第二个数，在找到解后跳过双指针的重复值。每一层去重都确保不会产生重复的四元组。虽然四数之和的时间复杂度更高，但通过排序、双指针和精细的去重处理，仍然能够高效地解决问题。

这两种算法都体现了将复杂问题分解为简单子问题的思想，通过排序和双指针技术将时间复杂度优化到可接受的范围，同时通过仔细的去重处理保证结果的正确性。

2.5 核心代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret; // 存储结果的容器
        
        // 先对数组进行排序，这是双指针解法的基础
        // 排序后可以方便地使用双指针，并且便于去重
        sort(nums.begin(), nums.end()); // 例如排序后：[-1, -1, 0, 0, 1, 2]

        int n = nums.size();
        
        // 第一层循环：固定第一个数
        for (int i = 0; i < n;) {
            // 第二层循环：固定第二个数
            for (int j = i + 1; j < n;) {
                int a = nums[i], b = nums[j]; // 当前固定的两个数
                
                // 将四数之和转化为两数之和问题：
                // nums[left] + nums[right] = target - nums[i] - nums[j]
                int left = j + 1, right = n - 1;
                
                // 使用 long long 防止整数溢出
                long long aim = (long long)target - nums[i] - nums[j];
                
                // 双指针在 j+1 到 n-1 的区间内寻找两数之和等于 aim
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    
                    if (sum < aim) {
                        left++; // 和太小，左指针右移
                    } else if (sum > aim) {
                        right--; // 和太大，右指针左移
                    } else {
                        // 找到满足条件的四元组
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        
                        // 移动指针继续寻找其他可能的解
                        left++;
                        right--;
                        
                        // 去重：跳过左侧重复的元素
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        // 去重：跳过右侧重复的元素
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                
                // 去重：跳过与当前 nums[j] 相同的元素，避免重复的四元组
                while (j + 1 < n && nums[j] == nums[j + 1]) j++;
                j++; // 移动到下一个不同的数字
            }
            
            // 去重：跳过与当前 nums[i] 相同的元素，避免重复的四元组
            while (i + 1 < n && nums[i] == nums[i + 1]) i++;
            i++; // 移动到下一个不同的数字
        }
        
        return ret;
    }
};