一、前言

  收到读者私信说：为什么你的算法越讲越简单了？
  我告诉他：因为你越来越聪明了！
  今天要讲的算法，《算法导论》书上是看不到的，因为无论是思考过程还是代码实现上都是非常容易理解的，所以各大算法书上都不屑将它归为算法，但是它却作为职场面试，省赛水题的绝佳选择，它有一个比较优雅的名字叫 尺取法，英文把它叫 “two pointers”，也就是 “双指针” 的意思。
  现在几点来着？四点？哈哈，早睡早起，方能养生！

二、最长不重复子串

• 接下来，以一个非常经典的面试题【最长不重复子串】为例，展开今天算法的讲解。

【例题1】给定一个长度为 $n (1 \le n \le 10^7)$ 的字符串 $s$，求一个最长的满足所有字符不重复的子串。

1、初步分析

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

2、朴素算法

• 由以上分析，我们可以发现第（1）个 和 第（4）个关键词给我们得出的结论是矛盾的，那么，我们可以先尝试减小 $n$ 的范围，如果 $n \le 1000$ 时，怎么解决这个问题呢？
• 因为最后求的是满足条件的最长子串，所以我们如果能够枚举所有子串，那么选择长度最长的满足条件的子串就是答案了（这里的条件是指子串中所有字符都不同）。

用 $ans$ 记录我们需要求的最大不重复子串的长度，用一个哈希表 $h$ 来代表某个字符是否出现过，算法描述如下：
  1）枚举子串的左端点 $i = 0 \to n-1$；
  2）清空哈希表 $h$；
  3）枚举子串的右端点 $j = i \to 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& l, int& r) {
    int ans = 0, i, j, len;
    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)$。
• 最后奉上一张动图，代表了上述朴素算法的求解过程，如图二-2-1所示：

图二-2-1

• 字符串下标从 0 开始，最长无重复子串为：$s[1:5] = bcaed$，长度为 5。
• 由于是字符串，字符集的个数 $z$ 最多 256，所以时间复杂度基本就是 $O(256n)$，当 $n \le 10^7$ 时，这个时间复杂度是无法接受的，需要想办法优化。

3、优化算法

• 如果仔细思考上面朴素算法的求解过程，就会发现：枚举子串的时候有很多区间是重叠的，所以必然存在许多没有必要的重复计算。
• 我们考虑一个子串以 $s_i$ 为左端点，$s_j$ 为右端点，且 $s[i:j-1]$ 中不存在重复字符，$s[i:j]$ 中存在重复字符（换言之，$s_j$ 和 $s[i:j-1]$ 中某个字符相同）。如图二-3-1所示：

图二-3-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 \gt k$，换言之， $i$ 可以一直自增，直到 $i = k+1$，如图二-3-2所示：

图二-3-2

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

int getmaxlen(int n, char *str, int& l, int& 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)$ 。
• 利用该优化算法优化后的最长不重复子串的求解过程如图二-3-3所示：

图二-3-3

• 参考这个图，一个比较通俗易懂的解释：当区间 $[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$++；
• 如图三-2-1 所示，当区间 $[i, j]$ 满足条件时，用蓝色表示，此时 $j$ 自增；反之闪红，此时 $i$ 自增。

图三-2-1

3、条件

• 这里所说的条件比较模糊，对于【例题1】来说，条件就是 “字符不重复”，当然也可以是 “每个字符重复次数不超过 $k$ 次”，”至少包含 $k$ 种字符”，”求和不大于 $k$” 等等，因题而异。
• 然而，无论问题怎么变，这里的条件都需要满足以下两点：

1）单调性

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

2）时效性

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

四、尺取法的应用

1、前缀和问题

【例题2】给定 $n (n \lt 10^5)$ 个正数 $a_i ( a_i \le 10^4)$ 和一个正数 $p(p < 10^8)$。找到一个最短的连续子序列，满足它的和 $s \ge p$。

• 对于一个连续子序列 $a[i:j]$，它的所有数之和为 $s[i:j] = \sum_{k=i}^{j} a_k$，如果我们已经知道 $s[i:j] \ge p$，那么就没必要再去求 $s[i:j+1]$，因为题目要求一个最短的连续子序列，所以基于这点，它满足单调性。
• 并且，我们可以定义前缀和 $sum_i = \sum_{k=1}^{i} a_k$，这样就可以通过 $O(1)$ 的时间计算出连续子序列的和：
• $s[i:j] = \sum_{k=i}^{j} a_k = sum_j – sum_{i-1}$
• c++ 代码实现如下：

int getminlen(int n, int *sum) {
    int len = n + 1, i = 1, j = 0;
    while (j++ < n) {
        while (sum[j] - sum[i - 1] >= p) {
            len = min(len, j - i + 1);
            ++i;
        }
    }
    if (len == n + 1) len = 0;
    return len;
}
复制代码

2、哈希问题

【例题3】对于一个字符串，如果它的每个字符数都 $\le k$，则称其为 $good$ 串。给定一个长度为 $n(1 \le n \le 10^5)$ 且只包含小写字母的字符串，求它的 $good$ 串的数量。

• 如果某个子串 $s[i: j]$ 是 $good$ 串，而 $s[i-1: j]$ 不是，那么可以得出：以 $j$ 为右端点的情况下，左端点只要大于等于 $i$，那么这个串一定是 $good$ 串，所以以 $j$ 为右端点，满足条件的个数为 $j-i+1$；
• 所以整个调整过程就是：$j$ 自增的过程，如果满足每个字符数都 $\le k$ 的情况下，累加 $j – i + 1$；否则，自增 $i$，继续判断可行性。每个字符的个数统计就用到了哈希。
• c++ 代码实现如下：

int has[256];
ll getcount(int n, char* str, int k) {
    ll ans = 0;
    int s = 0, i = 0, j = -1;
    memset(has, 0, sizeof(has));
    while (j++ < n - 1) {
        if (++has[str[j]] > k)
            s = 1;
        while (s) {
            if (--has[str[i]] == k)
                s = 0;
            ++i;
        }
        ans += (j - i + 1);
    }
    return ans;
}
复制代码

3、K 大数问题

【例题4】给定 $n ( n \le 200000)$ 个数 $a_i$，以及一个数 $m$，求第 $k$ 大的数 $\ge m$ 的区间的个数。

• 可以这么考虑：如果一个区间里面 $\ge m$ 的数不小于 $k$ 个，那么第 $k$ 大的也一定满足 $\ge m$。
• 于是我们将原数组作如下处理：将所有 $\ge m$ 的数变成 1，其它为 0，然后求出前缀和 $sum_i$。
• 那么对于某个区间 $[i, j]$，如果 $sum_{j} – sum_{i-1} \ge k$，则所有区间 $[i, k] (j \ge k \ge n)$ 都满足 “第 $k$ 大的数 $\ge m$“。所有以 $i$ 为左端点的满足条件区间数就是 $n-j+1$ 个；累加到答案。
• 并且满足 $sum_{j} – sum_{i-1} \ge k$ 时，左指针 $i$ 自增。
• c++ 代码实现如下：

#define ll long long
ll getcount(int n, int k) {
    ll ans = 0;
    int i = 1, j = 0;
    while (j++ < n) {
        while (sum[j] - sum[i - 1] >= k) {
            ans += n - j + 1;
            ++i;
        }
    }
    return ans;
}
复制代码

• 关于 尺取法 的内容到这里就全部结束了，如果还有不懂的问题可以留言告诉作者或者添加作者的微信公众号。

• 本文所有示例代码均可在以下 github 上找到：github.com/WhereIsHero…

五、尺取法相关题集整理