双指针算法模型定义

双指针算法本质剖析: 从起源, 到优化, 到双指针, 到变形

双指针经典例题分析总结

目前分类:

• 单调性双指针

  $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;
    }
};