双指针算法技巧全场景拆解：从数组操作到环检测

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        for (; dest < (int)arr.size() - 1; cur++) {
            if (arr[cur] == 0) dest++;
            dest++;
        }
        cur--;
        if (dest == arr.size()) {
            arr[arr.size() - 1] = 0;
            dest -= 2;
            cur--;
        }
        for (; cur >= 0; cur--) {
            arr[dest] = arr[cur];
            if (arr[cur] == 0) arr[--dest] = 0;
            dest--;
        }
    }
};

快乐数

题目链接： 202. 快乐数

思路： 结果只有两种可能：为 1 或者无限循环。对于无限循环的情况，可以使用快慢双指针去解决（类似链表判环）。快慢指针的起点都是 n，快慢指针一定会在环入口相遇。

class Solution {
public:
    int algorithm(int p) {
        int sum = 0;
        while (p >= 10) {
            int q = p % 10;
            p /= 10;
            sum += q * q;
        }
        sum += p * p;
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = n;
        slow = algorithm(slow);
        fast = algorithm(algorithm(fast));
        while (slow != fast) {
            slow = algorithm(slow);
            fast = algorithm(algorithm(fast));
        }
        return slow == 1;
    }
};

盛最多水的容器

题目链接： 11. 盛最多水的容器

思路：

• left 放在最左边，right 放在最右边。
• 比较之后，看 left 和 right 哪个对应的值小些，就把哪个向另外一边靠近。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int max1 = 0;
        while (left != right) {
            max1 = max(max1, (right - left) * min(height[right], height[left]));
            if (height[left] < height[right]) left++;
            else right--;
        }
        return max1;
    }
};

有效三角形的个数

题目链接： 611. 有效三角形的个数

思路：

• 相关数学知识：三角形最小的那两边之和 > 最大那一边就可以构成三角形了。
• 方法：先给数组排序，然后先固定最大的数，在最大的数的左边用双指针算法去找符合的数；然后再缩小最大的数。
• 注意：如果 nums[left] + nums[right] > nums[c]，那么 right - left 就是第二大数下标为 right 时的总个数，然后 right--。

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

查找总价格为目标值的两个商品

题目链接： 两数之和 II - 输入有序数组

思路：

• 这个题有单调性，用双指针正好（或者二分算法），能用双指针肯定优先用双指针。
• 注意：此题没说找不到怎么办，就不用管那种情况，但是力扣要求所有路径都要有返回值，在最后加个 return 即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> ret;
        int left = 0;
        int right = price.size() - 1;
        while (left != right) {
            if (price[left] + price[right] > target) right--;
            else if (price[left] + price[right] < target) left++;
            else {
                ret.push_back(price[left]);
                ret.push_back(price[right]);
                break;
            }
        }
        return ret;
    }
};

三数之和

题目链接： 三数之和

思路：

• 这种和怎么样怎么样的一般都排序之后用双指针。
• 细节问题：
  1. 去重：left 和 right 以及固定的那个数都要跳过重复元素（哪个跟哪个比较 == 才去要注意），同时要避免越界，比如 left 一直要 < right。
  2. 不漏：找到一种结果之后，不能直接 break 出去，要继续寻找，例如 left++; right--;。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int size = nums.size();
        for (int k = 0; k < size - 2; k++) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1;
            int j = size - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum > 0) j--;
                else if (sum < 0) i++;
                else {
                    ret.push_back({nums[k], nums[i], nums[j]});
                    i++;
                    j--;
                    while (i < j && nums[i] == nums[i - 1]) i++;
                    while (i < j && nums[j] == nums[j + 1]) j--;
                }
            }
        }
        return ret;
    }
};