双指针

前言

《算法导论》上是看不到的双指针的，因为无论是思考过程还是代码实现上都是非常容易理解，所以各大算法书上都不屑将它归为算法，但是它却作为职场面试，省赛水题的绝佳选择，它有一个比较优雅的名字叫 尺取法，英文把它叫 two pointers，也就是 双指针 的意思。需要注意的是，这个算法一般而言跟指针关系不大，不要被名字骗了……

一、最长不重复子串

给定一个长度为 n (1 ≤ n ≤ 10^7^) 的字符串 s，求一个最长的满足所有字符不重复的子串。

1、初步分析

首先我们分析一下这个问题的关键词，主要有以下几个：

1）n ≤ 10^7^；

2）最长；

3）所有字符不重复；

4）子串；

根据以上的几个关键词，我们可以得出一些结论。首先，根据 n 的范围已经能够大致确认这是一个需要 O(n) 或者 O(nlogn) 的算法才能解决的问题；其次，“最长” 这个词告诉我们，可能是一个动态规划问题或者贪心问题，也有可能是搜索，所以这个关键词给我们的信息用处不大；而判断字符是否重复可以用哈希表在 O(1) 的时间内判断；最后，枚举所有 “子串” 的时间复杂度是 O(n^2) 的。

2、朴素算法

由以上分析，我们可以发现第（1）个和第（4）个关键词给我们得出的结论是矛盾的，那么，我们可以先尝试减小 n 的范围，如果 n ≤ 1000 时，怎么解决这个问题呢？

因为最后求的是满足条件的最长子串，所以我们如果能够枚举所有子串，那么选择长度最长的满足条件的子串就是答案了（这里的条件是指子串中所有字符都不同）。

用 ans 记录我们需要求的最大不重复子串的长度，用一个哈希表 h 来代表某个字符是否出现过，算法描述如下：

1）枚举子串的左端点 i = 0 -> n-1；

2）清空哈希表 h；

3）枚举子串的右端点 j = i -> n-1，如果当前这个字符 s[j] 出现过（即 h[ s[j] ] 为 true），则跳出 j 的循环；否则，令 h[ s[j] ] 为 true，并且用当前长度去更新 ans（即 ans= max(ans, j - i +1) ）；

4）回到 2）；

c语言实现如下：

int getmaxlen(int n, char *str) {
    int ans = 0, i, j, len;
    int l, r;
    memset(h, 0, sizeof(h));
    for(i = 0; i < n; ++i) { // 1)
        j = i;
        memset(h, false, sizeof(h)); // 2)
        while(j < n && !h[str[j]]) {
            h[ str[j] ] = true; // 3)
            len = j - i + 1;
            if(len > ans)
                ans = len, l = i, r = j;
            ++j;
            }
        }
        return ans;
}

1）这一步枚举对应子串的左端点 i；

2）这一步用于清空哈希表 h，其中 h[ s[j] ] 为 true 代表原字符串的第 j 个字符 s[j] 是否出现在以第 i 个字符为左端点的子串中；

3）而第三步可以这么理解：如果字符串 s[i:j] 中已经出现重复的字符，那么 s[i:j+1]，s[i:j+2], … , s[i:n-1] 必然会有重复字符，所以这里不需要继续往下枚举，直接跳出第二层循环即可。

这个算法执行完毕，ans 就是我们要求的最长不重复子串的长度，[l, r] 代表了最长不重复子串在原字符串的区间。正确性毋庸置疑，因为已经枚举了所有子串的情况，如果字符集的个数 z，算法的时间复杂度就是 O(nz)。

最后奉上一张动图，代表了上述朴素算法的求解过程，如图所示：

字符串下标从 0 开始，最长无重复子串为：s[1:5] = bcaed，长度为 5。

由于是字符串，字符集的个数 z 最多 256，所以时间复杂度基本就是 O(256n)，当 n ≤ 10^7 时，这个时间复杂度是无法接受的，需要想办法优化。

3、优化算法

如果仔细思考上面朴素算法的求解过程，就会发现：枚举子串的时候有很多区间是重叠的，所以必然存在许多没有必要的重复计算。

我们考虑一个子串以 s[i] 为左端点，s[j] 为右端点，且 s[i:j-1] 中不存在重复字符，s[i:j] 中存在重复字符（换言之，s[j] 和 s[i:j-1] 中某个字符相同）。

那么我们没必要再去检测 s[i:j+1]，s[i:j+2]，s[i:n-1] 这几个字符串的合法性，因为当前情况 s[i:j] 是非法的，而这些字符串是完全包含 s[i:j] 的，所以它们必然也是不合法的。

那么我们可以把枚举的左端点自增，即： i = i +1，这时，按照朴素算法的实现，右端点需要重置，即 j = i，而实际上这里的右端点可以不动。

可以这么考虑，由于 s[j] 这个字符和 s[i:j-1] 中的字符产生了重复，假设这个重复的字符的下标为 k，那么 i 必须满足 i ≥ k，换言之， i 可以一直自增，直到 i = k+1，如图所示

利用上述思路，我们重新实现最长不重复子串的算法，C语言代码实现如下：

int getmaxlen(int n, char *str) {
    int l, r;
    int ans = 0, i = 0, j = -1, len; // 1)
    memset(h, 0, sizeof(h)); // 2)
    while (j++ < n - 1) { // 3)
        ++h[ str[j] ]; // 4)
        while (h[ str[j] ] > 1) { // 5)
            --h[ str[i] ];
            ++i;
        }
        len = j - i + 1;
        if(len > ans) // 6)
        ans = len, l = i, r = j;
    }
    return ans;
}

1）初始化 i = 0, j = -1，代表 s[i:j] 为一个空串，从空串开始枚举；

2）同样需要维护一个哈希表，哈希表记录的是当前枚举的区间 s[i:j] 中每个字符的个数；

3）只推进子串的右端点；

4）在哈希表中记录字符的个数；

5）当 h[ str[j] ] > 1 满足时，代表出现了重复字符，这时候左端点 i 推进，直到没有重复字符为止；

6）记录当前最优解 j-i+1；

这个算法执行完毕，我们就可以得到最长不重复子串的长度为 ans，并且 i 和 j 这两个指针分别只自增 n 次，两者自增相互独立，是一个相加而非相乘的关系，所以这个算法的时间复杂度为 O(n) 。

利用该优化算法优化后的最长不重复子串的求解过程如图所示：

参考这个图，一个比较通俗易懂的解释：当区间 [i, j] 中存在重复（红色）字符时，左指针 i 自增；否则，右指针 j 自增。

二、双指针

1、算法定义

如上文所述，这种利用问题特性，通过两个指针，不断调整区间，从而求出问题最优解的算法就叫 “尺取法”，由于利用的是两个指针，所以又叫 “双指针” 算法。

这里 “尺” 的含义，主要还是因为这类问题，最终要求解的都是连续的序列（子串），就好比一把尺子一样，故而得名。

2、算法描述

算法描述如下：

1）初始化 i=0, j=i-1，代表一开始 “尺子” 的长度为 0；

2）增加 “尺子” 的长度，即 j = j +1；

3）判断当前这把 “尺子” [i, j] 是否满足题目给出的条件：

3.a）如果不满足，则减小 “尺子” 长度，即 i = i + 1，回到 3）；

3.b）如果满足，记录最优解，回到 2）；

上面这段文字描述的比较官方，其实这个算法的核心，只有一句话：

满足条件时，j++；不满足条件时，i++；

如图所示，当区间 [i, j] 满足条件时，用蓝色表示，此时 j 自增；反之闪红，此时 i 自增。

3、条件

这里所说的条件比较模糊，对于【例题1】来说，条件就是 “字符不重复”，当然也可以是 “每个字符重复次数不超过 k 次”，“至少包含 k 种字符”，“求和不大于 k” 等等，因题而异。

然而，无论问题怎么变，这里的条件都需要满足以下两点：

1）单调性

所谓单调性，就是说：任意一个指针的增加，条件满足与否只会出现两种情况，即：【满足 -> 不满足】或者【不满足 -> 满足】，不会出现【满足 -> 不满足 -> 满足】这样的情况。

2）时效性

所谓时效性，就是说：必须在 O(1) 或者 O(log_2n) 的时间内，求出当前区间 [i, j] 是否满足既定条件，否则无法用这种算法求解。

三、习题

3. 无重复字符的最长子串 - 力扣（LeetCode）

392. 判断子序列 - 力扣（LeetCode）

11. 盛最多水的容器 - 力扣（LeetCode）