双指针算法详解与经典题目实战

1. 从左到右遍历不行 cur 需要判断的数据被 dest 覆盖，原因在于 dest 在 cur 之后进行了操作。如果是'删除等于 val 值'这类题目中，dest 始终保持在 cur 前面，因此不会出现数据被覆盖的情况。

2. 转化角度 如果从左往右遍历会出现数据覆盖的情况，可以尝试从右往左进行覆盖，从结果的最后一个数字开始，按逆序遍历。

算法思路

步骤分为两个阶段：

1. 定位结果的最后一个元素：可以使用双指针法遍历数组，此过程中无需修改数据，只需找到结果中的最后一个有效元素，并确定 dest 与 cur 应指向的位置。
2. 从右往左进行覆盖：在确定了结果末尾位置后，再从右向左逐步覆盖数据。

第一步：找到最后一个'复写'的数 通过推导输入与输出元素的位置关系，我们发现 cur 指向最后一个有效元素（例如数字 4），而 dest 指向数组的末尾。如果保留原始的两个 0 元素，则 cur 与 dest 之间相差 2，这表明 0 元素的数量会影响 dest 和 cur 的移动步幅。

第二步：移动数据

• 遇到非零元素：交换数据 arr[dest--] = arr[cur];
• 遇到零元素：重复两次 arr[dest--] = 0;

特殊情况处理 这里需要进行特殊处理：当 dest 达到 n 时，可能会导致数据覆盖，从而引发越界访问。

// 特殊情况处理，处理完也是需要对位置进行移动的
if (dest == n) { 
    arr[n - 1] = 0; 
    dest -= 2; 
    cur--; 
}

代码展示：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1. 先找到最后一个位置
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n) {
            if (arr[cur] == 0) dest += 2;
            else dest++;
            if (dest >= n - 1) break;
            cur++;
        }
        // 2. 特殊情况处理，处理完也是需要对位置进行移动的
        if (dest == n) { 
            arr[n - 1] = 0; 
            dest -= 2; 
            cur--; 
        }
        // 3. 开始数据处理
        while (cur >= 0) {
            if (arr[cur]) arr[dest--] = arr[cur];
            if (arr[cur] == 0) { 
                arr[dest--] = 0; 
                arr[dest--] = 0; 
            }
            cur--;
        }
    }
};

个人思考：在需要判断和修改数组元素的问题中，通常会想到双指针方法。但若从左到右遍历，可能会导致数据覆盖，从而影响结果。对此，不妨尝试调整遍历方向，说不定会带来意想不到的优化效果。

202.快乐数 [快慢指针]

题目展示：202.快乐数

示例 1：输入：n = 19 输出：true 解释：1² + 9² = 82; 8² + 2² = 68; 6² + 8² = 100; 1² + 0² + 0² = 1

算法思路

1. 是否为闭环 如果题目中没有提示'重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1'，那么我们必须额外判断以下三种情况，以确保程序能够正确终止：

   • 情况一：一直在 1 中死循环，即 1->1->1
   • 情况二：在历史的数据中死循环，但始终变不到 1
   • 情况三：单路线不断变化新数字，不是死循环

2. 闭环会限制变化的范围 因此，我们需要判断该数在变化过程中是否会形成闭环。形成闭环意味着至少会重复出现一次相同的数，此时数值变化的范围已被锁定。

3. 证明鸽巢原理 鸽巢原理：n 个巢，n + 1 个鸽，至少有一个巢，里面的鸽数大于 1，必有一个重复。那么意味着，只需要确定了 [1, n] 范围，就说明到 n + 1 必有一个重复的。而这个最大的 n，是可以通过一个最大数去推。 数据范围：1 <= n <= 2^31 - 1，选一个更大的数 9999999999。通过变化的最大值 9^2 * 10 = 810，那么变化的区间在 [1, 810] 之间。根据鸽巢原理，当一个数变化到 811 次之后，必然会形成一个循环。当形成一个闭环时，可以使用我们的快慢指针解决。

具体步骤：

• 当快慢指针相遇，相遇位置的值是 1，那么这个数一定是快乐数
• 当快慢指针相遇，相遇位置的值不是 1，那么这个数不是快乐数

代码展示：

class Solution {
public:
    int sum(int n) {
        int ret = 0;
        while (n) {
            int tmp = n % 10;
            ret += tmp * tmp;
            n /= 10;
        }
        return ret;
    }
    bool isHappy(int n) {
        // 定义快慢指针
        int slow = n;
        int fast = sum(n);
        while (slow != fast) {
            slow = sum(slow);
            fast = sum(sum(fast));
        }
        return slow == 1;
    }
};

个人思考：在这个问题中，我们需要根据需求特性判断是否形成闭环，而闭环的判断条件就是是否出现重复数。最初，这个思路并不容易想到，但可以借助鸽巢原理，通过数据的最大值来推导可能的变化范围。因此，在求解范围时，可以考虑是否能利用数据的最大值来确定 n 的界限。闭环会限制变化的范围。

11.盛水最多容器 [对撞指针、单调性]

题目展示：盛水最多容器

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49

题目解析：

1. 解法一：暴力求解 (会超时) 枚举出能构成的所有容器，找出其中容积最⼤的值，直接两层 for 循环，枚举能构成容器的体积，求得最大值。

   class Solution {
   public:
       int maxArea(vector<int>& height) {
           int n = height.size();
           int ret = 0;
           // 两层 for 枚举出所有可能出现的情况
           for (int i = 0; i < n; i++) {
               for (int j = i + 1; j < n; j++) {
                   // 计算容积，找出最⼤的那⼀个
                   ret = max(ret, min(height[i], height[j]) * (j - i));
               }
           }
           return ret;
       }
   };
   

2. 解法二：对撞指针

   算法思路 首先，我们需要理解如何计算容器的体积。通过设置 left 和 right 两个指针，分别指向容器的左边和右边，然后根据短板效应来决定水的高度，即水的高度由两边中较短的那块木板决定。

   公式：

   int v = min(height[left], height[right]) * (right - left);
   

   这里 v 代表容器的体积，其中有两个变量控制体积：height 和 width。height 是水的高度，width 是容器的宽度。

   假设左边木板比右边木板短（即短板在左边），我们可以从这里分析水的容积变化。

   容积变化的分析：

   1. 容器的宽度会变小：无论我们如何调整左或右边界，容器的宽度始终会减小（wide ↓），这意味着容积的变化必然受到宽度减少的影响。
   2. 移动左边界（短木板）：改变左边界 (短木板)，由于左边界较小，新的水面高度不确定，但是不会超过右边界的高度，因此容器的容积可能会增大，导致 v（未知） = w↓ * h（未知，可以增大）
   3. 移动右边界（长木板）：由于右边界较大，无论有边界移动到哪里，新的水面高度一定不会超过左边界，意味着当前高度 h 不变，由于宽度不断变小，对于容积一定会变小的。v↓ = w↓ * h（↓ 或者 不变）

   当我们移动短木板，这里因为 h 的不确定性，导致了容积可大可小。对此，当我们记录完一个区间的体积，将短木板往长木板靠拢，不间断判断下一个边界情况，不断刷新最大的容积。

   代码展示：

   class Solution {
   public:
       int maxArea(vector<int>& height) {
           // 需要取最小的数据
           int left = 0;
           int right = height.size() - 1;
           int ret = 0;
           while (left < right) {
               // 算体积
               int v = min(height[left], height[right]) * (right - left);
               // 更新最大的体积
               ret = max(ret, v);
               if (height[left] <= height[right]) left++;
               else right--;
           }
           return ret;
       }
   };
   

   个人思考：遇到这类涉及公式计算最值的问题时，可以利用单调性来简化分析。关键在于如何选择移动边界：移动长木板时，容积必然减小，而移动短木板时，容积变化不确定，但有可能增大。 本质上，问题的核心是利用单调性，从大到小向内枚举，逐步更新容积。每次移动边界时，更新容积并与当前最大值进行比较，最终得到最大的容积。

611.有效三角形的个数 [对撞指针、单调性]

题目展示：611.有效三角形的个数

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

算法思路

1. 数学知识：如何通过三个数，判断是否能构成三角形

   // 只需要两边之和大于第三边
   a + b > c
   a + c > b
   b + c > a
   

2. 解法一：暴力解法 通过暴力枚举法，可以使用三层 for 循环遍历所有可能的三角形数据，记录并筛选出符合条件的组合。

   for (i = 0; i < n; i++)
       for (j = i + 1; j < n; j++)
           for (k = j + 1; k < n; k++)
               check(i, j, k);
   

   通过数学优化，当 a <= b <= c 时，判断三角形成立只需验证 a + b > c。因为在这种情况下，c 是最大的，a + c 和 b + c 必然大于另一个边。优化步骤：首先对数组进行排序，得到有序数组。

   时间复杂度 没有进行优化，三层 for 循环的时间复杂度就是 O(N^3)。如果进行了优化，时间复杂度就是 O(NlogN + N^3)。虽然时间复杂度是取主要影响的变量，但是不管如何，这里进行了优化的情况下，时间复杂度是得到了优化，同时处理数据方面也是得到改善。

3. 解法二：对撞指针 提示：借鉴上次容积问题的思路，**当根据公式或表达式判断条件时，可以利用单调性优化。**通过固定最大数，并使用 left 和 right 指针指向左右两端，避免枚举。类似容积问题，从左到右或从右到左的差异源自数据大小顺序，影响判断条件的判断效率。

   通过设置两个变量作为边界，首先判断 a + b 是否大于 c。如果 a + b > c，那么从左到右时，a + b 会始终大于 c，无需再继续枚举；从右到左时，a + b 的大小关系不确定，因此需要保留这个操作进行整体判断。如果 a + b <= c，则从右到左会使 b 变小，导致无法满足条件，因此需要移动 left，使得 a + b 不断逼近并超过 c。在此过程中，left 和 right 会不断调整，因此需要在循环内进行相应的更新。

   这里的 sum += right - left 表示以 right 为边界时，所有满足条件的组合数量。

   代码展示：

   class Solution {
   public:
       int triangleNumber(vector<int>& nums) {
           sort(nums.begin(), nums.end());
           int n = nums.size();
           int sum = 0;
           for (int i = n - 1; i >= 2; i--) {
               int left = 0, right = i - 1;
               while (left < right) {
                   if (nums[left] + nums[right] > nums[i]) {
                       sum += right - left;
                       right--;
                   } else {
                       left++;
                   }
               }
           }
           return sum;
       }
   };
   

179.和为 s 的两个数字 [对撞指针、单调性]

题目展示：179.和为 s 的两个数字 (原题目))

输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]

算法思路

这道题属于基础题，主要考察双指针法在单调性匹配中的应用。关键是判断 left + right == target。

对于 left + right ? target，共有三种情况。通过利用单调性，依据 left 和 right 指向的数据关系，调整它们的位置以达到目标。

代码展示：

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, right = price.size() - 1;
        while (left < right) {
            int sum = price[left] + price[right];
            // 连续判断还是写 else if 分支语句
            if (sum > target) right--;
            else if (sum < target) left++;
            else return {price[left], price[right]};
        }
        // 为了照护编译器，通过返回 -1
        return {-1, -1};
    }
};

15.三数之和 [对撞指针、单调性]

题目展示：15.三数之和

输入：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] 。注意，输出的顺序和三元组的顺序并不重要。

首先分析题目给出的信息，注意到题目没有明确说明是否允许重复三元组。因此，需要通过实例来推断是否存在重复三元组的情况。

题目中说明三元组的顺序不重要，因此我们关注的是数据是否重复。通过例子 [-1, 0, 1]、[0, 1, -1] 和 [-1, 1, 0]，我们可以发现这些是重复的三元组。为了简化判断，可以统一将三元组排序为 [-1, 0, 1]，通过排序来优化，避免不必要的重复判断。

解法一：排序 + 暴力枚举 + 利用 set 去重：时间复杂度 O(N^3)

解法二：对撞指针

根据题目需求，我们需要统计满足 nums[a] + nums[left] + nums[right] == 0 的三元组。可以将其转化为 nums[left] + nums[right] = -nums[a]，这意味着当 nums[left] + nums[right] 等于 nums[a] 的相反数时，条件成立。通过固定一个数值并移动两个边界，我们能够减少不必要的枚举次数。

个人思考：这个问题和两数之和的单调性问题类似，只需固定一个数并让另两个数的和等于目标值，之后通过调整左右指针来查找所有满足条件的组合。

细节问题

如果使用 set 来去重，则需要额外的时间来插入和查找每个元素，时间复杂度为 O(log n)。我们通过排序的方法，将 [-1, 0, 1]、[0, 1, -1]、[-1, 1, 0] 重复的数据统一变成了 [-1, 0, 1] 的形式，但是重复的数据，我们是不需要的。固定一个数，当 left 和 right 指向位置符合要求后，就需要考虑重复问题，进行去重操作。当然不止 left 和 right 需要去重，固定的数据也需要完成去重操作，避免越界 [0, 0, 0, 0]。

代码展示：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> v;
        // 排序下
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 2;) {
            // 不存在 nums[]+nums[] = minPositive_nums[i]
            if (nums[i] > 0) break;
            int left = i + 1, right = n - 1;
            int target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else {
                    // 初始化列表自动转为 vector<int> 类型
                    v.push_back({nums[left], nums[right], nums[i]});
                    left++;
                    right--;
                    // 去重判断
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重操作
            // 这里会导致判断时，造成越界访问
            // while(nums[i] == nums[i + 1]) i++;
            i++;
            // 关于越界访问，需要判断循环逻辑是否有问题。
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return v;
    }
};

18.四数之和 (三数之和 Plus) [对撞指针、单调性]

题目展示：18.四数之和

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

算法思路

这里同样的，按照题目要求可以得到一个表达式 nums[a] + nums[b] + nums[left] + nums[right] == target,按照我们熟悉的解法，我们是通过固定一个数，以 left 和 right 两个数作为边界向内进行查找。但是这里多出了一个数，那么不妨可以这样 nums[b] + nums[left] + nums[right] == target - nums[a]，跟三数之和题目不是一样了吗？这里多次一个数的意义，就是多了一层循环。

解法一：排序 + 暴力枚举 + 利用 set 去重 时间复杂度 O(N^4)

解法二：对撞指针

问题：栈溢出

对此这里需要考虑数据的范围将 dest 和 target 类型转化为 long long

代码展示：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // -4 - 3 -2 -1
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> v;
        for (int i = 0; i < n - 3;) {
            for (int j = i + 1; j < n - 2;) {
                // 新的目标数
                long long dest = (long long)target - nums[i] - nums[j];
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum > dest) right--;
                    else if (sum < dest) left++;
                    else {
                        v.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 - 2 && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n - 3 && nums[i] == nums[i - 1]) i++;
        }
        return v;
    }
};