ID: 19267

传统题

1000ms

32MiB

尝试: 3

已通过: 1

难度: 10

上传者:

tobyforever

标签>

模板

原网页 https://labuladong.online/algo/essential-technique/array-two-pointers-summary/

你好！我是你的OI竞赛教练。

今天我们深入讲解 数组双指针（Array Two Pointers） 技巧。

这一类问题通常要求原地修改（In-place）或者时间复杂度 $O(N)$ ，是空间复杂度优化和时间复杂度优化的利器。我们将这一章分为两大派系：快慢指针 和 左右指针。

OI 专题：数组双指针技巧汇总

Topic: Two Pointers Technique on Arrays

第一部分：快慢指针 (Fast & Slow Pointers)

应用场景：通常用于解决“原地修改数组”问题，如去重、移除元素、移动零等。 核心定义：

fast 指针：探路者。在前探索，寻找如果不删除/不修改应该保留的元素。
slow 指针：构建者。维护“新数组”的尾部，只有当 fast 找到有效元素时，slow 才向前移动并接收数据。

1. 有序数组去重 (Remove Duplicates)

题目：给定一个有序数组 nums，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。思路：因为是有序的，重复元素一定相邻。我们让 slow 指向当前唯一序列的末尾，fast 向前扫描。如果 nums[fast] != nums[slow]，说明找到了一个新元素，把它搬到 slow 的下一格。

OI 风格代码实现：

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    // slow: 维护去重后数组的最后一个有效元素的下标
    int slow = 0;
    // fast: 遍历寻找新元素的探针
    for (int fast = 0; fast < nums.size(); ++fast) {
        if (nums[fast] != nums[slow]) {
            // 找到了新元素
            slow++;
            nums[slow] = nums[fast];
        }
    }
    // 长度是下标 + 1
    return slow + 1;
}

2. 移除元素 (Remove Element)

题目：原地移除数组中所有等于 val 的元素。思路：依然是快慢指针。fast 遇到 val 就跳过；fast 遇到非 val，就把它赋值给 slow，并让 slow 前进。 教练口诀：“Fast 只管走，遇到非删元素就喂给 Slow。”

OI 风格代码实现：

int removeElement(vector<int>& nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.size(); ++fast) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow; // slow 指向的是新数组长度（即下一个写入位置）
}

3. 移动零 (Move Zeroes)

题目：将数组中所有 0 移动到末尾，保持非零元素的相对顺序。思路：这就是“移除元素”的变体。第一步：利用上面的逻辑，移除所有 0（把非零元素往前挤）。第二步：把 slow 之后的所有位置填充为 0。

OI 风格代码实现：

void moveZeroes(vector<int>& nums) {
    // 1. 类似 removeElement，移除所有 0
    int slow = 0;
    for (int fast = 0; fast < nums.size(); ++fast) {
        if (nums[fast] != 0) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    // 2. 将剩余部分置为 0
    while (slow < nums.size()) {
        nums[slow] = 0;
        slow++;
    }
}

第二部分：左右指针 (Left & Right Pointers)

应用场景：二分查找、两数之和、反转数组、回文串判断。 核心定义：

left 指针：指向数组/字符串开头（Index 0）。
right 指针：指向数组/字符串末尾（Index N-1）。
动作：两个指针相向而行，直到相遇 (left == right) 或交错 (left > right)。

1. 两数之和 II - 输入有序数组 (Two Sum - Sorted)

题目：在有序数组中找到两个数，使它们相加等于 target。思路：暴力法是 $O(N^2)$ 。利用有序性，我们可以 $O(N)$ 解决：

如果 sum < target：我们要让和变大，只能让 left 右移（变大的方向）。
如果 sum > target：我们要让和变小，只能让 right 左移（变小的方向）。

OI 风格代码实现：

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            // 题目要求下标从1开始
            return {left + 1, right + 1};
        } else if (sum < target) {
            left++; // 让和变大
        } else {
            right--; // 让和变小
        }
    }
    return {-1, -1};
}

2. 反转数组 (Reverse Array)

题目：原地反转一个字符数组或字符串。思路：最基础的左右指针。交换 left 和 right 的内容，然后向中间收缩。

OI 风格代码实现：

void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        // swap 是 <algorithm> 中的标准函数，OI常用
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

3. 二分查找 (Binary Search)

虽然二分查找通常单独作为一类算法，但本质上它就是左右指针的一种应用。区别：两数之和是每次移动一步，二分查找是每次折半移动。

OI 风格代码实现：

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) { // 注意是 <=
        // 防止溢出的中点写法
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else 
            right = mid - 1;
    }
    return -1;
}

第三部分：回文串专题 (Palindrome - Center Expansion)

回文串问题是左右指针的经典变体。判断回文是从两边向中间缩，而寻找回文串通常是从中间向两边扩（中心扩散法）。

1. 判断回文串

思路：左右指针向中间逼近，如果字符不相等则非回文。

OI 风格代码实现：

bool isPalindrome(string s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

2. 最长回文子串 (Longest Palindromic Substring)

题目：给你一个字符串 s，找到 s 中最长的回文子串。难点：回文串长度可能是奇数（中心是一个字符，如 aba），也可能是偶数（中心是两个字符，如 abba）。技巧：中心扩散法 (Center Expansion)。我们遍历每一个字符，分别以该字符为中心（奇数情况）和以该字符及下一个字符之间为中心（偶数情况）向外扩散。

OI 风格代码实现：

// 辅助函数：从中心向两端寻找回文串，返回该回文串
string palindrome(const string& s, int l, int r) {
    // 防止索引越界，并判断是否满足回文条件
    while (l >= 0 && r < s.size() && s[l] == s[r]) {
        l--; // 向左扩展
        r++; // 向右扩展
    }
    // while 终止时，s[l] 和 s[r] 已经不相等了（或者越界）
    // 回文串范围是 [l+1, r-1]
    // substr(pos, len) -> pos = l + 1, len = r - 1 - (l + 1) + 1 = r - l - 1
    return s.substr(l + 1, r - l - 1);
}

string longestPalindrome(string s) {
    string res = "";
    for (int i = 0; i < s.size(); i++) {
        // 1. 以 s[i] 为中心（奇数长度，如 aba）
        string s1 = palindrome(s, i, i);
        // 2. 以 s[i] 和 s[i+1] 为中心（偶数长度，如 abba）
        string s2 = palindrome(s, i, i + 1);
        
        // 更新最长结果
        if (s1.length() > res.length()) res = s1;
        if (s2.length() > res.length()) res = s2;
    }
    return res;
}

课后总结 (Coach's Summary)

同学们，做双指针题目时，脑子里要有两个“小人”在数组上跑的画面：

快慢指针：
- 关键词：原地修改、去重、保序移动。
- 画面：fast 在前面开路挖宝，slow 在后面拿着篮子接宝，没用的东西直接丢弃。
左右指针：
- 关键词：二分、两数之和、反转、回文。
- 画面：两个小人从两头往中间走（相向），或者从中间往两头跑（背向/扩散）。

掌握了这两种模型，处理线性数组 $O(N)$ 复杂度的题目时，你将游刃有余。下节课我们将把双指针技巧应用到链表中，敬请期待！

课后习题：

刚才我们讲了快慢指针和左右指针。为了让你彻底掌握“左右指针”在有序数组中的变体应用，我精选了一道非常经典的题目。

这道题看似简单，但如果直接暴力做是 $O(N \log N)$ ，而利用双指针技巧可以优化到 $O(N)$ 。它是检验你是否真正理解“有序数组利用两端特性”的试金石。

课后练习题：能量石的强度排序 (Squares of a Sorted Array)

【题目描述】

小明收集了一排能量石，每块石头都有一个能量基数 $A_i$ （可能为负数）。这些石头原本是按照能量基数非递减顺序（从小到大）排列的。但是，石头的真实战斗力是能量基数的平方。

现在小明想知道，如果把这些石头按照真实战斗力（即 $A_i^2$ ）也从小到大重新排列，结果会是什么？

请你编写一个程序，在 $O(N)$ 的时间复杂度内完成排序。

【输入格式】

第一行包含一个正整数 $N$ ，表示能量石的数量。第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ，表示每块石头的能量基数。数据保证 $A$ 数组是非递减的（即有序）。

【输出格式】

输出一行，包含 $N$ 个整数，表示按真实战斗力（平方值）从小到大排列的结果。

【样例 1】

输入

5
-4 -1 0 3 10

输出

0 1 9 16 100

解释：原数组：[-4, -1, 0, 3, 10] 平方后：[16, 1, 0, 9, 100] 排序后：[0, 1, 9, 16, 100]

【样例 2】

输入

5
-7 -3 2 3 11

输出

4 9 9 49 121

【数据范围】

$1 \le N \le 10^5$
$-10^4 \le A_i \le 10^4$
$A$ 数组已按非递减顺序排列。

【解题思路提示】

1. 暴力法（不推荐） 先把所有数平方，然后调用 sort()。

时间复杂度： $O(N \log N)$ 。
虽然能过，但在面试或高阶竞赛中，这不算完美解法。

2. 双指针法（推荐） 仔细观察原数组：[-4, -1, 0, 3, 10]。因为数组是有序的，平方后的最大值一定出现在数组的“两端”（要么是最大的正数平方，要么是最小的负数平方）。

左边可能很大（比如 -100 的平方是 10000）。
右边也可能很大（比如 100 的平方是 10000）。
中间的数字平方后反而比较小（接近 0）。

策略：我们使用 左右指针，分别指向数组的头 (left) 和尾 (right)。

比较 nums[left]^2 和 nums[right]^2。
谁大，谁就是当前剩余元素中的“老大”。
把这个“老大”填入结果数组的末尾（从后往前填）。
被选中的指针向中间移动一格。

【参考代码 (C++14 OI Style)】

见题解

【自我检查】

循环条件：为什么是 while (left <= right) 而不是 <？
- 因为当 left == right 时，还剩最后一个元素（通常是最小的那个），我们也需要把它填入结果数组中。
填充顺序：为什么要从 pos = n-1 开始填？
- 因为双指针找到的是“最大值”，如果从 0 开始填，你需要把它们反转或者用复杂的逻辑找最小值。逆序填充是最顺手的。

#19267. 数组双指针

数组双指针

OI 专题：数组双指针技巧汇总

第一部分：快慢指针 (Fast & Slow Pointers)

1. 有序数组去重 (Remove Duplicates)

2. 移除元素 (Remove Element)

3. 移动零 (Move Zeroes)

第二部分：左右指针 (Left & Right Pointers)

1. 两数之和 II - 输入有序数组 (Two Sum - Sorted)

2. 反转数组 (Reverse Array)

3. 二分查找 (Binary Search)

第三部分：回文串专题 (Palindrome - Center Expansion)

1. 判断回文串

2. 最长回文子串 (Longest Palindromic Substring)

课后总结 (Coach's Summary)

课后练习题：能量石的强度排序 (Squares of a Sorted Array)

【题目描述】

【输入格式】

【输出格式】

【样例 1】

【样例 2】

【数据范围】

【解题思路提示】

【参考代码 (C++14 OI Style)】

【自我检查】

状态

开发

支持

关于

#19267. 数组双指针

数组双指针

OI 专题：数组双指针技巧汇总

第一部分：快慢指针 (Fast & Slow Pointers)

1. 有序数组去重 (Remove Duplicates)

2. 移除元素 (Remove Element)

3. 移动零 (Move Zeroes)

第二部分：左右指针 (Left & Right Pointers)

1. 两数之和 II - 输入有序数组 (Two Sum - Sorted)

2. 反转数组 (Reverse Array)

3. 二分查找 (Binary Search)

第三部分：回文串专题 (Palindrome - Center Expansion)

1. 判断回文串

2. 最长回文子串 (Longest Palindromic Substring)

课后总结 (Coach's Summary)

课后练习题：能量石的强度排序 (Squares of a Sorted Array)

【题目描述】

【输入格式】

【输出格式】

【样例 1】

【样例 2】

【数据范围】

【解题思路提示】

【参考代码 (C++14 OI Style)】

【自我检查】

状态

开发

支持

关于

还没有账户？

登录