【优选算法篇】两队接力跑：双指针协作解题的艺术（下篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

接上篇：【优选算法篇】两人赛跑解难题：双指针算法的妙用（上篇）-CSDN博客

引言：通过上篇文章带大家简单了解“双指针算法”，小试牛刀。接下来将让大家感受一下双指针在解题的妙处。

在算法面试中，双指针是一种非常高效的技巧，能够帮助我们在许多问题中快速定位解。它不仅能大大降低时间复杂度，还能优化空间使用，提升整体程序性能。C++ 作为一种具有高效内存管理和指针操作能力的语言，使得双指针算法得以在众多场景下应用得淋漓尽致。本文将介绍 C++ 双指针算法的进阶技巧，并通过经典问题讲解如何巧妙地运用这一技术。

“C++ 双指针进阶：高效解题的秘密武器”

1. C++ 双指针算法进阶详解

1.1 双指针的基本概念

双指针算法的基本思路是使用两个指针（或索引）同时遍历数据，常常用于有序数组或链表等数据结构中。两个指针可以向相同方向移动，也可以相向而行。通过调整指针的位置，我们能够在复杂度上进行优化。

1.1.1 基本应用场景：

• 查找数组中的一对数：给定一个有序数组，找出和为指定目标值的两数。
• 字符串问题：寻找不含重复字符的最长子串、回文子串等。

2. 题目1：盛最多水的容器

题目链接：11. 盛最多水的容器 - 力扣（LeetCode）

题目描述：

补充：

2.1 算法思路：

2.1.1 核心思想

采用双指针法，从数组的两端开始，逐步向中间靠拢，通过调整指针位置，找到可以容纳最多水的两个柱子。

思考过程

1. 初始状态： 容器的两条边分别为数组的第一个和最后一个元素，对应指针为 left 和 right。
2. 计算容量： 容量由两条柱子中较短的一根高度和两指针之间的距离决定：容量=min(height[left],height[right])×(right−left)
3. 指针调整： 为了找到更大的容量，移动较短的那条柱子对应的指针。
   • 如果 height[left] < height[right]，左指针右移（left++）。
   • 否则，右指针左移（right--）。
4. 终止条件： 当 left 和 right 相遇时，遍历结束。

关键点

• 容量由两条柱子中较短的一根高度决定，因此移动较短的柱子有可能找到更大的容积。
• 双指针法避免了暴力解法的多次重复计算，将时间复杂度从 O(n^2)优化为 O(n)。

2.1.2 解析示例

输入：

height = [1,8,6,2,5,4,8,3,7]

输出：

49

步骤：

1. 初始化 left = 0, right = 8，容量： volume=min(1,7)×(8−0)=7×8=49
2. 移动较短的柱子：left = 1，此时 height[left] = 8。
3. 再次计算容量，移动较短的柱子：
   • 比较 height[left] 和 height[right]，更新 max_volume，直至 left == right。
4. 最终得到最大容量：49。

2.2 示例代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 初始化双指针，一个指向数组最左边(left)，一个指向数组最右边(right)
        // 初始化变量 ret 用于存储最大容积，初始值为 0
        int left = 0, right = height.size() - 1, ret = 0;

        // 当左右指针未相遇时，继续遍历
        while (left < right) {
            // 计算当前容器的容量，取两根柱子中较短的一根作为高度
            // 容积公式为：短板高度 * 两指针之间的距离
            ret = max(ret, min(height[left], height[right]) * (right - left));

            // 根据较短的一根柱子移动指针，尝试寻找更大的容量
            if (height[left] < height[right]) {
                // 如果左边的柱子较短，移动左指针
                left++;
            } else {
                // 如果右边的柱子较短，移动右指针
                right--;
            }
        }

        // 返回最终找到的最大容积
        return ret;
    }
};

2.3 复杂度分析

• 时间复杂度： O(n)。每次迭代中，左右指针只移动一次，总共遍历 n个元素。
• 空间复杂度： O(1)。仅使用了常量空间存储指针和容量变量。

2.4 总结：

双指针通过从两端向中间收缩并动态调整计算条件，避免了暴力解法的多次重复计算，能够在最短时间内找到结果。这种思路同样适用于很多类似的优化问题，比如“接雨水”、“最小覆盖子串”等，掌握它会让你的算法能力更上一层楼。

3. 题目2：有效三角形个数

题目链接：611. 有效三角形的个数 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

3.1.1 排序

将数组 nums 按升序排序，使得对于任意 i<j<k，我们有：nums[i]≤nums[j]≤nums[k]

这样只需验证 nums[i]+nums[j]>nums[k]，即可保证满足三角形条件。

3.1.2 双指针遍历

对于每个 k（即三角形中最长的边），尝试找到符合条件的 i , j：

1. 固定 k 为当前最长边，从数组的右侧向左遍历。
2. 初始化两个指针：
   • i=0：指向数组的起点。
   • j=k−1：指向 k 左侧的最后一个元素。
3. 检查三角形条件：
   • 如果 nums[i]+nums[j]>nums[k]，则对于所有i≤t≤j 的 t，都满足 nums[t]+nums[j]>nums[k]，因此三角形个数增加 j−i，然后移动 j 左移。
   • 否则，将 i 右移。

3.2 示例代码：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 对数组进行排序
        sort(nums.begin(), nums.end());
        int count = 0;

        // 遍历每个可能的最长边
        for (int k = nums.size() - 1; k >= 2; --k) {
            int i = 0, j = k - 1;

            // 双指针查找符合条件的边
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    // 符合条件的三角形个数
                    count += (j - i);
                    --j; // 移动右指针
                } else {
                    ++i; // 移动左指针
                }
            }
        }

        return count;
    }
};

3.3 复杂度分析

• 时间复杂度： 排序的时间复杂度为 O(nlog⁡n)，双指针遍历的时间复杂度为 O(n^2)，总复杂度为 O(n^2)。
• 空间复杂度： 仅使用了常量空间，空间复杂度为 O(1)。

3.4 总结：

该算法通过排序和双指针的结合，有效地减少了重复计算，是解决三角形个数问题的经典方法。排序后的双指针遍历不仅逻辑简单，而且复杂度低，非常适合处理大规模数据。

4. 题目3： 查找总价格为目标值的两个商品

题目链接：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

题目描述:

4.1 算法思路：

具体步骤：

• 排序： 首先，数组必须是有序的。如果数组是无序的，可以先进行排序。
• 初始化指针： 定义两个指针，left 指向数组的开始，right 指向数组的末尾。
• 循环：
  • 计算 price[left] + price[right]。
  • 如果和小于目标值 target，说明左指针的元素过小，可以向右移动左指针（left++）。
  • 如果和大于目标值 target，说明右指针的元素过大，可以向左移动右指针（right--）。
  • 如果和等于目标值，返回这两个价格。
• 结束条件： 当 left 指针与 right 指针重合时，说明没有找到符合条件的商品，返回 {-1, -1}。

4.2 示例代码：

class Solution
{
public:
    vector<int> twoSum(vector<int>& price, int target)
    {
        vector<int> ret;
        // 双指针算法
        int left = 0, right = price.size() - 1;
        
        while (left < right) {
            int sum = price[left] + price[right];  // 计算当前两个指针所指向元素的和
            if (sum < target) {
                left++;  // 如果和小于目标值，左指针右移
            } else if (sum > target) {
                right--;  // 如果和大于目标值，右指针左移
            } else {
                return {price[left], price[right]};  // 如果找到目标和，返回结果
            }
        }
        
        return {-1, -1};  // 如果没有找到符合条件的商品，返回{-1, -1}
    }
};

4.3 复杂度分析：

• 时间复杂度：
  • 在最坏情况下，算法需要遍历整个数组一次。每次移动指针的操作都是常数时间复杂度 O(1)，因此总时间复杂度为 O(n)，其中 n 是数组 price 的长度。
• 空间复杂度：
  • 使用了常量的额外空间来存储指针和结果，因此空间复杂度为 O(1)。

4.4 总结：

双指针法适合于在已排序的数组中查找满足特定条件的元素对。它利用了数组的顺序性，通过调整指针来高效地减少计算量，从而在 O(n) 时间内找到目标结果。对于本题，双指针法是一个非常高效的解决方案。

5. 题目四：三数之和

题目链接：15. 三数之和 - 力扣（LeetCode）

题目描述：

这个问题可以通过排序 + 双指针法来高效解决，时间复杂度为 O(n^2)，因为每个元素都会遍历一次，同时使用双指针来寻找满足条件的两数。

5.1 算法思路：

5.1.1 具体步骤：

1. 排序：
   • 首先，我们对数组 nums 进行排序，以便可以利用双指针法。排序后的数组有助于后续检查重复的三元组，避免重复计算。
2. 固定一个数，利用双指针求解其他两个数：
   • 遍历数组，固定每个数 nums[i]，然后使用双指针法在 nums[i+1] 到 nums[n-1] 的区间内寻找其他两个数，使得这三个数之和为零。
   • 双指针操作：
     • 使用两个指针，left 和 right，分别指向当前区间的两端。根据 nums[i] 和 nums[left] + nums[right] 的和与零的关系来决定如何移动指针：
       • 如果 nums[left] + nums[right] > -nums[i]，则将 right 向左移动，减小和。
       • 如果 nums[left] + nums[right] < -nums[i]，则将 left 向右移动，增加和。
       • 如果 nums[left] + nums[right] == -nums[i]，则找到一个三元组，将其加入结果，并移动两个指针，跳过相同的元素以避免重复三元组。
3. 避免重复：
   • 固定 nums[i] 后，若 nums[i] 和前一个元素相同，则跳过当前元素，避免重复。
   • 在双指针移动时，若 nums[left] 与 nums[left-1] 相同，或者 nums[right] 与 nums[right+1] 相同，跳过这些元素以避免重复。
4. 返回结果：
   • 最终，所有符合条件的三元组将被保存在 ret 向量中，返回该向量。

5.2 示例代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;

        sort(nums.begin(), nums.end());  // 先对数组进行排序
        int n = nums.size();
        
        for (int i = 0; i < n - 2;) {  // 固定一个数
            int left = i + 1, right = n - 1;
            
            // 双指针寻找其余两个数
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum > 0) {
                    right--;  // 总和大于0，右指针左移
                } else if (sum < 0) {
                    left++;  // 总和小于0，左指针右移
                } else {
                    // 找到一个和为0的三元组
                    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--;
                }
            }
            
            // 跳过重复的元素
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }

        return ret;
    }
};

5.3 复杂度分析：

• 时间复杂度：
  • 排序操作的时间复杂度为 O(nlog⁡n)，其中 n 是数组 nums 的长度。
  • 双指针部分的时间复杂度为 O(n^2)，因为外层循环会执行 n 次，而内层双指针部分最多会执行 n 次。最终的总时间复杂度是 O(n^2)。
• 空间复杂度：
  • 除了返回的结果 ret，我们只使用了常量空间来存储指针和临时变量。因此空间复杂度是 O(1)，不过需要注意返回的结果所占的空间是与结果大小相关的。

5.4 总结：

• 通过排序和双指针法，可以有效地减少搜索的时间复杂度，将问题的时间复杂度优化为 O(n^2)。
• 为了避免重复三元组，在排序后的数组中，需要在固定元素和双指针移动过程中跳过重复的元素。
• 此算法适用于查找所有和为零的三元组，能够在给定的时间和空间限制内高效地解决问题。

6. 题目5：四数之和

题目链接：18. 四数之和 - 力扣（LeetCode）

题目描述：

为了高效解决此问题，我们可以利用排序和双指针法来避免暴力解法的高时间复杂度。

6.1 算法思路：

• 排序：
  • 首先，将数组 nums 进行排序。这有助于后续使用双指针法，并且排序后的数组有助于跳过重复的元素，避免重复的四元组。
• 固定前两个数：
  • 固定数组中的前两个数 nums[i] 和 nums[j]，接下来使用双指针法来找出剩下两个数使得四个数的和等于 target。
• 使用双指针法：
  • 对于每一对固定的 nums[i] 和 nums[j]，在剩下的元素中使用双指针法来寻找另外两个数 nums[left] 和 nums[right]，使得四个数的和为 target。
  • 计算当前四个数的和 sum = nums[i] + nums[j] + nums[left] + nums[right]。
  • 如果 sum 小于 target，则需要增大 sum，所以将左指针 left 向右移动；如果 sum 大于 target，则需要减小 sum，所以将右指针 right 向左移动。
  • 如果 sum 等于 target，则找到一个符合条件的四元组，添加到结果列表 ret 中，并且移动指针以跳过重复的元素。
• 跳过重复元素：
  • 每次固定一个数之后，如果下一个元素与前一个元素相同，则跳过该元素，以避免重复的四元组。
  • 在双指针的过程中，当发现左指针 left 和右指针 right 指向相同的元素时，也应该跳过，以避免重复。
• 返回结果：
  • 当所有可能的四元组都被检查完后，返回所有符合条件的四元组。

6.2 示例代码：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());  // 对数组进行排序
        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;
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j];  // 当前两个数的和
                    long long t = (long long)target - nums[left] - nums[right];  // 剩余的目标和
                    
                    if (sum > t) {
                        right--;  // 总和大于目标值，右指针左移
                    } else if (sum < t) {
                        left++;  // 总和小于目标值，左指针右移
                    } 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++;
                while (j < n && nums[j] == nums[j - 1]) j++;  // 跳过重复的元素
            }
            
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;  // 跳过重复的元素
        }
        
        return ret;
    }
};

6.3 复杂度分析：

• 时间复杂度：
  • 排序数组的时间复杂度为 O(nlog⁡n)，其中 n 是数组 nums 的长度。
  • 外层循环遍历数组的每个元素，共有 n 次。
  • 内层循环也是通过双指针法来寻找四元组，对于每个 i 和 j，在最坏情况下，双指针遍历剩余部分的时间复杂度是 O(n)。因此，双指针的总时间复杂度是 O(n^2)。
  • 总体时间复杂度为 O(n^2)，其中排序的时间复杂度是 O(nlog⁡n)，因此总时间复杂度为 O(n^2)。
• 空间复杂度：
  • 除了结果数组 ret，我们只使用了常数空间来存储指针和临时变量。因此，空间复杂度为 O(1)，但结果数组的空间占用与结果大小有关。

6.4 总结：

• 通过固定前两个数和使用双指针法，我们将问题从暴力求解的O(n^4)优化到O(n^2)。
• 排序和跳过重复元素保证了最终返回的结果不包含重复的四元组。
• 这种方法适合处理需要查找多个数的组合和满足特定条件的情况下，具有较高的效率和较低的空间复杂度。

7.代码对比特点

8. 最后

通过上述「盛最多水的容器」、「有效三角形个数」、「查找目标值的两个商品」、「三数和」以及「四数和」的例子，可以总结出双指针算法的核心思想、应用场景和优化技巧。双指针算法高效、灵活，特别适合处理有序数组中的查找、优化与统计问题。通过上述例子，我们可以看到双指针的优势在于减少搜索空间，同时通过排序和跳过重复优化结果。掌握双指针方法是解决数组与组合类问题的利器。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！