【优选算法篇】双指针的华丽探戈：深入C++算法殿堂的优雅追寻

C++ 双指针详解：进阶题解与思维分析

💬 欢迎讨论：如有疑问或见解，欢迎在评论区留言互动。

👍 点赞、收藏与分享：如觉得这篇文章对您有帮助，请点赞、收藏并分享！
🚀 分享给更多人：欢迎分享给更多对 C++ 感兴趣的朋友，一起学习双指针的基础与进阶！

前言

接上篇【优选算法篇】双指针的优雅舞步：C++ 算法世界的浪漫探索

本篇文章将带领大家进入双指针的进阶领域。在基础篇中，我们已经学习了如何利用双指针优化简单数组问题，而在这一篇中，我们将进一步深入探讨双指针的高级应用场景，包括排序问题、多数之和等经典题型的双指针解法，以及如何利用双指针快速解决复杂的数组与链表问题。

通过更加深入的题目分析和双指针的高级策略，我们希望大家能够更加熟练地运用这一算法技巧，应对更具挑战性的编程问题。让我们继续双指针的优雅舞步，开启 C++ 算法世界的浪漫探索！

第一章：有效三角形的个数

1.1 有效三角形的个数

题目链接：611. 有效三角形的个数
题目描述：给定一个包含非负整数的数组 nums，返回其中可以组成三角形三条边的三元组个数。

示例 1：

• 输入：nums = [2, 2, 3, 4]
• 输出：3
• 解释：有效的组合是：
  • 2, 3, 4 （使用第一个 2）
  • 2, 3, 4 （使用第二个 2）
  • 2, 2, 3

示例 2：

• 输入：nums = [4, 2, 3, 4]
• 输出：4
• 解释：
  • 4, 2, 3
  • 4, 2, 4
  • 4, 3, 4
  • 2, 3, 4

解法一（暴力求解）

算法思路：

• 三层 for 循环枚举出所有的三元组，并判断是否能构成三角形。
• 判断三角形的优化：
  • 如果能构成三角形，需要满足任意两边之和大于第三边。但实际上只需让较小的两条边之和大于第三边即可。
  • 因此可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三角形。

代码实现：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1. 排序
        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 0;
        // 2. 从小到大枚举所有的三元组
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // 当最小的两个边之和大于第三边的时候，统计答案
                    if (nums[i] + nums[j] > nums[k])
                        ret++;
                }
            }
        }
        return ret;
    }
};

复杂度分析：

• 时间复杂度：O(n^3)，对于较大的输入，三层循环会导致性能问题，适合小规模数据。
• 空间复杂度：O(1)，只使用了常数个变量存储结果和中间值。

解法二（排序 + 双指针）

算法思路：

• 先将数组排序。
• 根据「解法一」中的优化思想，可以固定一个「最长边」，然后在比这条边小的有序数组中找出一个二元组，使这个二元组之和大于这个最长边。由于数组是有序的，我们可以利用「对撞指针」来优化。
• 设最长边枚举到位置 i，区间 [left, right] 是 i 位置左边的区间（也就是比它小的区间）：
  • 如果 nums[left] + nums[right] > nums[i]：
    • 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比 nums[i] 大的二元组。
    • 满足条件的有 right - left 种。
    • 此时 right 位置的元素的所有情况相当于全部考虑完毕，right--，进入下一轮判断。
  • 如果 nums[left] + nums[right] <= nums[i]：
    • 说明 left 位置的元素不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组。
    • left 位置的元素可以舍去，left++ 进入下一轮循环。

代码实现：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利用双指针解决问题
        int ret = 0, n = nums.size();
        for (int i = n - 1; i >= 2; i--) { // 先固定最大的数
            // 利用双指针快速统计符合要求的三元组的个数
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
};

复杂度分析：

• 时间复杂度：O(n^2)，排序的时间复杂度为 O(n log n)，之后每个元素使用双指针进行一次遍历，时间复杂度为 O(n^2)。
• 空间复杂度：O(1)，只使用了常数个变量存储结果和指针位置。

易错点提示

1. 指针移动逻辑：在双指针遍历时，根据条件选择移动 left 或 right，确保找到所有满足条件的三元组。
2. 数组排序：在开始双指针遍历之前，必须对数组进行排序，否则无法保证正确性。
3. 三角形判定条件：确保只需判断两边之和是否大于第三边，简化条件判断，避免遗漏有效三元组。

代码解读

该算法的时间复杂度为 O(n^2)，空间复杂度为 O(1)，适合大规模输入。通过排序和双指针优化，能够有效减少暴力求解中的不必要计算，提升性能。此方法非常适合在数组问题中应用，能够快速找到所有满足条件的组合。

第二章：和为 s 的两个数字

2.1 和为 s 的两个数字

题目链接：剑指 Offer 57. 和为s的两个数字
题目描述：输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。

示例 1：

• 输入：nums = [2, 7, 11, 15], target = 9
• 输出：[2, 7] 或者 [7, 2]

解法一（暴力解法）

算法思路：

• 两层 for 循环列出所有两个数字的组合，判断是否等于目标值。

算法流程：

• 两层 for 循环：
  • 外层 for 循环依次枚举第一个数 a；
  • 内层 for 循环依次枚举第二个数 b，让它与 a 匹配；
  • 然后将挑选的两个数相加，判断是否符合目标值。

代码实现：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target)
                    return {nums[i], nums[j]};
            }
        }
        return {-1, -1};
    }
};

解法二（双指针 - 对撞指针）

算法思路：

• 注意到本题是升序的数组，因此可以使用「对撞指针」优化时间复杂度。

算法流程：

• 初始化 left，right 分别指向数组的左右两端：
  • 当 left < right 的时候，一直循环：
    • 当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并返回；
    • 当 nums[left] + nums[right] < target 时：
      • 说明当前和小于目标值，需要增大和，left++；
    • 当 nums[left] + nums[right] > target 时：
      • 说明当前和大于目标值，需要减小和，right--。

代码实现：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target) right--;
            else if (sum < target) left++;
            else return {nums[left], nums[right]};
        }
        //这是为了照顾编译器，不然编译器报错：不是所有的路径都有返回值
        return {-1, -1};
    }
};

第三章：三数之和与四数之和

3.1 三数之和

题目链接：15. 三数之和
题目描述：给你一个整数数组 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

解法（排序+双指针）

算法思路：

• 本题与两数之和类似，是非常经典的面试题。
• 与两数之和稍微不同的是，题目中要求找到所有「不重复」的三元组。我们可以利用双指针思想来对暴力枚举做优化：
  1. 先排序；
  2. 然后固定一个数 a；
  3. 在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。
• 需要注意的是，这道题中需要有「去重」操作：
  1. 找到一个结果之后，left 和 right 指针要「跳过重复」的元素；
  2. 当使用完一次双指针算法之后，固定的 a 也要「跳过重复」的元素。

代码实现：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利用双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) { // 固定数 a
            if (nums[i] > 0) break; // 小优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++, right--;
                    // 去重操作 left 和 right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重 i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

3.2 四数之和

题目链接：18. 四数之和
题目描述：给你一个由 n 个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。

示例 1：

• 输入：nums = [1, 0, -1, 0, -2, 2], target = 0
• 输出：[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

示例 2：

• 输入：nums = [2, 2, 2, 2, 2], target = 8
• 输出：[[2, 2, 2, 2]]

提示：

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

解法（排序 + 双指针）

算法思路：

1. 依次固定一个数 a；
2. 在这个数 a 的后面区间上，利用「三数之和」找到三个数，使这三个数的和等于 target - a 即可。

代码实现：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利用双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) { // 固定数 a
            for (int j = i + 1; j < n; ) { // 固定数 b
                // 双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                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--;
                    }
                }
                // 去重 j
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重 i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

写在最后

在本篇文章中，我们沿着双指针的足迹，走进了更为复杂的算法世界。从基础的排序与两数之和，到多元问题的优化解法，双指针以其灵活而高效的策略，为我们提供了简洁优雅的解题思路。无论是解锁数组中的隐藏结构，还是精确处理链表中的循环，双指针始终如同算法中的舞者，轻巧地穿梭于问题的复杂性之间，帮助我们化繁为简。

希望通过这些进阶题解，大家能不仅熟悉双指针的运用技巧，更能深刻体会到算法设计中的思维之美。未来的算法旅程中，无论面对怎样的挑战，双指针这一工具都能在你的编程工具箱中，成为应对复杂问题时得心应手的利器。

以上就是关于【优选算法篇】双指针的华丽探戈：深入C++算法殿堂的优雅追寻的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️