双指针算法本质剖析: 从起源, 到优化, 到双指针, 到变形
双指针经典例题分析总结
目前分类:
-
单调性双指针
$j = f(i)$ 单调性, 主要证明单调性
-
循环不变双指针
$(i,j)$ 表示一个循环不变对象, 主要证明循环不变式
二者应该是能够相互转化的
随着题目的增多, 会慢慢发现这两种方法本质上是一样的, 只不过思路不同, 角度不同, 证明的方法不同
单调性双指针
特征: $j = f(i)$ 单调性
类似于偏导数, 固定变量 $i$, 研究 $j$,
视角固定在 $i$ 上, 然后研究 $j$
循环不变双指针
特征: $(i,j)$ 表示循环不变量
类似于全导数, 将变量 $i$ 和 $j$ 放在一起研究
视角放眼全局, 研究各种情况下 $i$ 和 $j$ 的变化
最长连续不重复子序列
解法一: 单调性
$(i,j)$含义:
$(i,j)$ 指代某个区间
对于每个 $i$, $i$ 为区间右端点,
$j$ 表示所有不含重复元素区间 $[j,i]$ 中离 $i$ 最远的左端点
样例:
1 2 2 3 5
$i = 1$ 时, $j = 1$, 区间为 $[1,1]$
$i = 2$ 时, $j = 1$, 区间为 $[1,2]$
$i = 3$ 时, $j = 3$, 区间为 $[3,3]$
$i = 4$ 时, $j = 3$, 区间为 $[3,4]$
$i = 5$ 时, $j = 3$, 区间为 $[3,5]$
答案为所有满足条件 $(i,j)$ 中最长区间的长度, 即区间 $[3,5]$ 的长度 3
单调性证明:
对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$
需要说明 $j^{\prime}$ 与 $j$ 的大小关系
假定 $j^{\prime} < j$
根据定义可知 $[j^{\prime},i+1]$ 是不含重复元素的区间
$\therefore$ $[j^{\prime},i]$ 也是不含重复元素的区间
根据 $j = f(i)$ 的定义, 显然 $j^{\prime} \geq j$, 产生矛盾
$\therefore$ $j^{\prime} \geq j$, $j = f(i)$ 单调递增, 符合单调性
遍历方向:
由于 $j = f(i)$ 单调递增, 所以 $j$ 的遍历方向为 $1\rightarrow m$
结果:
所需结果为所有 $(i,j)$ 中最大区间的长度
核心代码:
int res = 0;
for(int i = 0, j = 0; i < n; i++)
{
cnt[a[i]]++;
while(j <= i && cnt[a[i]] > 1) cnt[a[j++]]--;
res = max(res, i - j + 1);
}
$~$
解法二: 循环不变
int res = 0;
cnt[a[0]]++;
for(int i = 0, j = 0; i < n && j <= i;)
{
if(cnt[a[i]] > 1) cnt[a[j++]]--;
else
{
res = max(res, i - j + 1);
cnt[a[++i]]++;
}
}
数组元素的目标和
解法一: 单调性
$(i,j)$含义:
$(i,j)$ 指代 $a_i+b_j$
对于每个 $i$, $j$ 表示满足 $a_i + b_j \leq x$ 的最大 $j$
样例:
a: 1 2 4 7
b: 3 4 6 8 9
x = 6
$i = 1$ 时, $j = 2$, 指代 1 + 4
$i = 2$ 时, $j = 2$, 指代 2 + 4
$i = 3$ 时, $j = 0$
$\dots$
所需结果为所有 $(i,j)$ 中与 x 相等的那个, 即 $(2,2)$
单调性证明:
对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$
需要说明 $j^{\prime}$ 与 $j$ 的大小关系
假定 $j^{\prime} > j$
则 $j^{\prime} \geq j + 1$
根据定义可知 $a_i + b_j \leq x$ 和 $a_i + b_{j+1} > x$
则 $a_{i+1} + b_{j^{\prime}} \geq a_i + b_{j+1} > x$
这与 $j^{\prime} = f(i + 1)$ 的含义矛盾
$\therefore$ $j^{\prime} \leq j$, $j = f(i)$ 单调递减, 符合单调性
遍历方向:
由于 $j = f(i)$ 单调递减, 所以 $j$ 的遍历方向为 $m \rightarrow 1$
结果:
所需结果为所有 $(i,j)$ 中与 x 相等的那个
核心代码:
for(int i = 0, j = m - 1; i < n; i++)
{
while(j >= 0 && a[i] + b[j] > x) j--;
if(j >= 0 && a[i] + b[j] == x)
输出答案
}
事实上, 如这个贴子的最后和下面所述, 这道题也可以用循环不变双指针的方法来做
$~$
解法二: 循环不变
for(int i = 0, j = m - 1; i < n && j >= 0;)
{
if(a[i] + b[j] == x)
输出答案
else if(a[i] + b[j] > x) j--;
else i++;
}
判断子序列
解法一: 单调性
$(i,j)$含义:
$(i,j)$ 指代当前匹配的进度
具体来说,
$i$ 表示 a 序列进度, 即 $[a_1,\dots,a_{i-1}]$ 均已在 b 序列中找到匹配对象, 当前正在寻找 $a_i$ 匹配对象
$j$ 表示在上述前提下尽可能靠左的与 $a_i$ 匹配的对象
样例:
a: 1 3 5
b: 1 2 3 4 5
$i = 1$ 时, $j = 1$
$i = 2$ 时, $j = 3$
$i = 3$ 时, $j = 5$
单调性证明:
对于 $j = f(i)$, 当 $i$ 递增后, 即 $j^{\prime} = f(i + 1)$
需要说明 $j^{\prime}$ 与 $j$ 的大小关系
假定 $j^{\prime} \leq j$
则与子序列的定义矛盾
$\therefore$ $j^{\prime} > j$, $j = f(i)$ 严格单调递增
换句话说, 就是显然 $j^{\prime} > j$
遍历方向:
由于 $j = f(i)$ 严格单调递增, 所以 $j$ 的遍历方向为 $1 \rightarrow m$
而且由于是严格单调递增, 所以代码与上面的两道题稍有不同
结果:
所需结果需要判断 $j = f(n)$ 是否合法
核心代码:
for(int i = 0, j = 0; i < n; i++)
{
while(j < m && a[i] != b[j]) j++;
if(j < m) j++; // j = f(i) 严格单调递增的影响
else
输出 No
}
输出 Yes
$~$
解法二: 循环不变
for(int i = 0, j = 0; i < n && j < m)
{
if(a[i] == b[j]) i++;
j++;
}
if(i == n)
输出 Yes
else
输出 No
验证回文串
解法一: 单调性
class Solution {
public:
bool isPalindrome(string s) {
for(int i = 0, j = s.size() - 1; i < j; i++)
{
if(!isalnum(s[i])) continue;
while(i < j && !isalnum(s[j])) j--;
if(i < j && tolower(s[i]) != tolower(s[j]))
return false;
else j--;
}
return true;
}
};
解法二: 循环不变
class Solution {
public:
bool isPalindrome(string s) {
for(int i = 0, j = s.size() - 1; i < j;)
{
if(isalnum(s[i]) && isalnum(s[j]))
{
if(tolower(s[i]) == tolower(s[j])) i++, j--;
else return false;
}
else
{
if(!isalnum(s[i])) i++;
if(!isalnum(s[j])) j--;
}
}
return true;
}
};
盛最多水的容器
解法一: 单调性
class Solution {
public:
int maxArea(vector<int>& arr) {
int res = 0;
for(int i = 0, j = arr.size() - 1; i < arr.size(); i++)
{
res = max(res, (j - i) * min(arr[i], arr[j]));
while(j > i && arr[j] < arr[i])
{
j--;
res = max(res, (j - i) * min(arr[i], arr[j]));
}
}
return res;
}
};
根据本题经典方法(循环不变)改写
改的时候有点艰难, 换个思路后的代码果然不好写
解法二: 循环不变
class Solution {
public:
int maxArea(vector<int>& arr) {
int res = 0;
for(int i = 0, j = arr.size() - 1; i < j;)
{
res = max(res, (j - i) * min(arr[i], arr[j]));
if(arr[i] <= arr[j]) i++;
else j--;
}
return res;
}
};
循环不变的证明思路可以参考这篇帖子
前置:
根据 for(int i = 0, j = arr.size() - 1; i < j;)
整个搜索空间呈倒三角形状
搜索空间坐标 $(i,j)$ 含义:
左上角为零点, $i$ 表示行坐标, $j$ 表示列坐标
图片可参考上面那个帖子, 不会画那么好看的动态图
证明:
$(i,j)$ 对应的循环不变式:
以 $(i,j)$ 为右上角顶点的倒三角区域为待搜索空间, 剩余搜索空间为已搜索空间, res 表示已搜索空间中容器的最大储水量
初始化:
$i = 0, j = arr.size() - 1, res = 0$
$(i,j)$ 对应整个搜索空间, 已搜索空间为空, res = 0, 显然成立
保持:
假设某轮循环开始前循环不变式成立
执行循环体
res = max(res, (j - i) * min(arr[i], arr[j])); // 搜索 (i,j) 点, 更新 res
if(arr[i] <= arr[j]) i++; // 排除该行的其他点, 证明下述
else j--; // 排除该列的其他点
定义 $S_{ij} = (j - i) \times \min(a[i],a[j])$, 即 $(i,j)$ 对应的储水量
若 $a[i] \leq a[j]$:
该行的其他点为 $(i,k), k \in (i,j)$
则 $S_{ik} = (k - i) \times \min(a[i],a[k])$
$\because$ $k < j$
$\therefore$ $k - i < j - i$
$\because$ $a[i] \leq a[j]$
$\therefore$ $\min(a[i],a[j]) = a[i]$
又 $\because$ $\min(a[i],a[k]) \leq a[i]$
$\therefore$ $\min(a[i],a[k]) \leq \min(a[i],a[j])$
$\therefore$ $S_{ik} < S_{ij}$
$\therefore$ 该行的其他点都可以排除掉
同理, $a[i] > a[j]$ 情况下该列的其他点都可以排除掉
$~$
根据 $a[i]$ 与 $a[j]$ 的大小关系可以排除该行或该列的其他点, 又因 $(i,j)$ 已搜索过, 所以该行或该列相当于搜索过
$\therefore$ 在 $i$ 或 $j$ 更新之后, 下一轮循环开始之前, 循环不变式成立
终止:
循环结束时, $i \geq j$, 则整个搜索空间已全部搜索, res 表示整个搜索空间中所有点的最大储水量
颜色分类
循环不变
感觉很不好改编成单调性做法
class Solution {
public:
void sortColors(vector<int>& arr) {
for(int i = 0, j = 0, k = 0; i < arr.size(); i++)
{
if(arr[i] == 0)
{
swap(arr[i], arr[j]);
swap(arr[j], arr[k]);
j++, k++;
}
else if(arr[i] == 1)
swap(arr[i], arr[j++]);
}
}
};
证明:
$(i,j,k)$ 对应的循环不变式:
$[0,k)$ 全 0, $[k,j)$ 全 1, $[j,i)$ 全 2, $a_i$ 为当前待搜索点, $[0,i)$ 为已排好序区间
初始化:
循环开始前 $i = j = k = 0$,
则区间全为空, 循环不变式成立
保持:
假设某轮循环开始前, 循环不变式成立
执行循环体
if(arr[i] == 0)
{
swap(arr[i], arr[j]);
swap(arr[j], arr[k]);
j++, k++;
}
else if(arr[i] == 1)
swap(arr[i], arr[j++]);
会将 $a[i]$ 交换到对应的位置, 且 $(i,j,k)$ 发生相应变化
这段分析并不难, 略过
所以 $(i,j,k)$ 更新之后, 下一轮循环开始之前, 循环不变式成立
终止:
循环结束时, $i = n$, 则说明区间 $[0,n)$ 已排好序, 符合题目要求
三数之和
单调性
两数之和的简单应用
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& arr) {
sort(arr.begin(), arr.end());
vector<vector<int>> res;
for(int i = 0; i < arr.size(); i++)
{
if(i && arr[i] == arr[i - 1]) continue;
for(int j = i + 1, k = arr.size() - 1; j < k; j++)
{
if(j > i + 1 && arr[j] == arr[j - 1]) continue;
while(j < k && arr[k] > -arr[i] - arr[j]) k--;
if(j < k && arr[k] == -arr[i] - arr[j])
res.push_back({arr[i], arr[j], arr[k]});
}
}
return res;
}
};
去重方式的分析:
关键代码
if(i && arr[i] == arr[i - 1]) continue; // 对 i 去重
if(j > i + 1 && arr[j] == arr[j - 1]) continue; // 对 j 去重, k 不需要去重
对 i 来说, 若 $a_i = a_{i+1}$
第一个元素为 $a_i$ 时, $j$ 和 $k$ 要从 $(i,n]$ 中选择
第一个元素为 $a_{i+1}$ 时, $j$ 和 $k$ 要从 $(i+1,n]$ 中选择
$\because$ $a_i = a_{i+1}$ 且明显第一个候选空间 $\{a_i,a_j,a_k\}$ 包含第二个候选空间 $\{a_{i+1},a_j,a_k\}$
$\therefore$ 这种情况下要直接跳过
删除有序数组中的重复项
循环不变
// 自己的想法
class Solution {
public:
int removeDuplicates(vector<int>& arr) {
int j = 0;
for(int i = 0; i < arr.size(); i++)
{
if(j && arr[i] == arr[j - 1]) continue;
else arr[j++] = arr[i];
}
return j;
}
};
// y 总的做法
class Solution {
public:
int removeDuplicates(vector<int>& arr) {
int j = 0;
for(int i = 0; i < arr.size(); i++)
{
if(i && arr[i] == arr[i - 1]) continue;
else arr[j++] = arr[i];
}
return j;
}
};
