双指针算法：从暴力遍历到线性高效重构数组操作 | 极客日志

C++算法

双指针算法：从暴力遍历到线性高效重构数组操作

双指针算法在数组操作中的核心应用，涵盖移动零、复写零、快乐数、盛水最多的容器、有效三角形个数、两数之和、三数之和及四数之和等经典题目。通过对比暴力解法与双指针优化方案，展示如何将时间复杂度从 O(n²) 或 O(n³) 降低至 O(n) 或 O(n log n)，并提供 C++ 代码实现及详细原理解析。

氛围发布于 2026/3/28更新于 2026/4/162 浏览

双指针算法：从暴力遍历到线性高效重构数组操作

前言

双指针算法并非真正的指针，而是利用数组下标模拟两个指针的移动。该技巧能将原本需要嵌套循环的 O(n²) 问题优化至 O(n)，实现花最少的力气办最大的事。

1、移动零

题目链接：https://leetcode.cn/problems/move-zeroes/description/

文章配图

算法原理

这类问题可以分为数组划分或者叫数组分块，并且使用双指针算法。

文章配图

指针作用：
- left：始终指向已处理区间内的最后一个非 0 元素处
- right：从左到右依次遍历数组
具体步骤：
- 利用 right 从左到右依次遍历的过程中：
- 遇到非 0 元素：left++，交换 left 和 right 处的元素，right++
- 遇到 0：right++
只要保证 left 始终在最后一个非 0 元素的位置，right 从左往右遍历即可

代码演示：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int right = 0, left = -1; right < nums.size(); right++) {
            if(nums[right]) swap(nums[right], nums[++left]);
        }
    }
};

2、复写零

题目链接：https://leetcode.cn/problems/duplicate-zeros/

文章配图

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 先找最后一个复写 0 的位置
        int cur = 0, dest = -1, n = arr.size();
        while(dest < n) {
            if(arr[cur]) dest++;
            else dest += 2;
            // 当 dest 等于 n-1 时，cur 指向最后一个要复写的元素，
            // dest 大于 n-1 代表，最后一个要复写的元素是 0，但是只有一个有效位置了
            if(dest >= n - 1) break;
            cur++;
        }
        // 处理边界
        if(dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 从后往前完成复写
        while(cur >= 0) {
            arr[dest--] = arr[cur];
            if(arr[cur] == 0) {
                arr[dest--] = 0;
            }
            cur--;
        }
    }
};

class Solution {
public:
    // 计算一个数各位数字的平方和
    int qdsum(int n) {
        int sum = 0;
        while(n) {
            int i = n % 10;
            sum += i * i;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n; // 慢指针：初始值为 n，每次计算 1 次平方和（走 1 步）
        int fast = qdsum(n); // 快指针：初始值为 n 的第一次平方和，每次计算 2 次平方和（走 2 步）
        // 没相遇就一直走
        while (slow != fast) {
            slow = qdsum(slow); // 慢指针走 1 步：计算当前值的平方和
            fast = qdsum(qdsum(fast)); // 快指针走 2 步：连续计算两次平方和
        }
        // 当快慢指针相遇时，若值为 1 则是快乐数，否则陷入非 1 的循环，不是快乐数
        if (slow == 1) return true;
        else return false;
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int ret = 0;
        while(left < height.size()) {
            // right 每次都从 left 的下一个位置开始穷举
            int right = left + 1;
            while(right < height.size()) {
                int v = (right - left) * min(height[left], height[right]);
                ret = max(v, ret);
                right++;
            }
            left++;
        }
        return ret;
    }
};

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

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int count = 0;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                for(int k = j + 1; k < nums.size(); k++) {
                    if(nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
};

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int count = 0;
        sort(nums.begin(), nums.end()); // 排序：为双指针优化做准备
        // 固定最大边 nums[n]，从后往前遍历（n 至少为 2，需 3 条边）
        for(int n = nums.size() - 1; n >= 2; n--) {
            int left = 0, right = n - 1;
            // 双指针：在 [0, n-1] 中找两条较小边
            while(left < right) {
                // 若当前两边和 > 最大边，说明 left 到 right-1 的所有边与 right 组合均满足条件
                if(nums[left] + nums[right] > nums[n]) {
                    count += (right - left); // 直接统计 right-left 个有效组合
                    right--; // 缩小右指针，继续判断更小的 right
                } else {
                    left++; // 两边和不足，增大左指针尝试更大值
                }
            }
        }
        return count;
    }
};

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

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0;
        int right = price.size() - 1;
        for(int i = 0; i < price.size(); i++) {
            int sum = price[left] + price[right];
            if(sum > target) {
                right--;
            } else if(sum < target) {
                left++;
            } else {
                // 列表初始化返回值：用大括号{}直接构造 vector<int>，包含找到的两个数值
                return {price[left], price[right]};
            }
        }
        // 列表初始化返回值：构造包含{-1,-1}的 vector<int>，作为未找到时的默认返回
        return {-1, -1};
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            // 去重 i：如果当前 i 和前一个 i 元素相同，跳过（避免重复枚举同一 i 对应的组合）
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j < n; j++) {
                // 保留当前层的第一个元素，只跳过后续的重复元素
                // 去重 j：如果当前 j 和前一个 j 元素相同，跳过
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                for(int k = j + 1; k < n; k++) {
                    // 去重 k：如果当前 k 和前一个 k 元素相同，跳过
                    if (k > j + 1 && nums[k] == nums[k - 1]) continue;
                    if(nums[i] + nums[j] + nums[k] == 0) {
                        vv.push_back({nums[i], nums[j], nums[k]});
                    }
                }
            }
        }
        return vv;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 1、排序
        sort(nums.begin(), nums.end());
        // 存放三元组的二维数组
        vector<vector<int>> vv;
        for(int i = 0; i < nums.size(); i++) {
            // 如果数据大于 0 了就不用在后面匹配了，因为后面的都是正数，两个正数相加不可能为负数，也就不可能等于 0 了
            if(nums[i] > 0) {
                break;
            }
            // i 不能提前去重，不然后面的 left 和 right 的匹配就会受到影响
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            // 二元组下标
            int left = i + 1;
            int right = nums.size() - 1;
            // left < right 就继续查找
            while(left < right) {
                // 固定位置值的相反数
                int sum = -nums[i];
                if(left < right && nums[left] + nums[right] == sum) // 存储最终结果
                {
                    // 满足条件的三元组进行尾插
                    vv.push_back({nums[i], nums[left], nums[right]});
                    // left 去重
                    // left < right 防止越界
                    left++;
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    // right 去重
                    // left < right 防止越界
                    right--;
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
                // 判断二元组的和和上一个题思路一样，我就不多注释了
                else if(left < right && nums[left] + nums[right] > sum) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return vv;
    }
};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();
        for(int a = 0; a < n;) // 固定第一个数
        {
            for(int b = a + 1; b < n;) // 固定第二个数
            {
                // 把 target-a-b 的值存起来，方便比较
                // 用 longlong 存储是因为，数值大点相减就超范围了
                long long ami = (long long)target - nums[a] - nums[b];
                // left 始终是固定的第二个数的下一个位置
                int left = b + 1;
                int right = n - 1;
                while(left < right) {
                    int sum = nums[left] + nums[right];
                    // 利用单调性去掉不必要的枚举，上面几个题有同样的思路
                    if(sum > ami) {
                        right--;
                    } else if(sum < ami) {
                        left++;
                    } else {
                        vv.push_back({nums[a], nums[b], nums[left++], nums[right--]});
                        // left 和 right 去重
                        while(left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while(left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
                // 固定的第二个数去重
                b++;
                while(b < n && nums[b] == nums[b - 1]) {
                    b++;
                }
            }
            // 固定的第一个数去重
            a++;
            while(a < n && nums[a] == nums[a - 1]) {
                a++;
            }
        }
        return vv;
    }
};