双指针算法

发表于 2021-11-02 更新于 2021-11-21 Artalk： loading...

前言

双指针算法

关于滑动窗口和双指针算法的区分–讨论
“经过与官方的一些讨论，目前将计算过程仅与「两端点」相关的称为「双指针」，将计算过程与「两端点表示的区间」相关的称为「滑动窗口」”

y总:可以考虑从朴素暴力做法开始思考

//朴素做法
for (int i = 0; i < m; ++ i) {
    for (int j = 0; j <= i; ++ j) {
        if (check(i, j)) {
            res = max(res, j - i + 1);
        }
    }
}

朴素做法，每次i指针到一个新的位置，j指针都会从0开始循环。

如果i指针每次前进，j指针也根据条件判断是否进行前进（j不后退，即当i前进时，达到的新的符合要求的状态时，j的位置一定在上一个符合要求状态之后），这样就可以用双指针算法来优化暴力循环，将时间复杂度从 $O(n^2)$ 降低到 $O(n)$ 。

例题

leetcode 3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), res = 0;
        unordered_map<char, int> hashmap;
        int l = 0, r = 0;
        while (r < n) {
            hashmap[s[r]] ++;
            while (hashmap[s[r]] > 1) {
                hashmap[s[l]] --;
                l ++;
            }
            res = max(res, r - l + 1);
            r ++;
        }
        return res;
    }
};

个人心得

首先观察题目

字符串问题，要求连续的子字符串，而非子序列（可以删除若干字符）时，可以考虑

在思考，若第一反应是可以暴力循环做的，尝试考虑双指针做法。

然后判断达成要求的状态是否满足「随着r指针前进，L指针可以不后退」

具体做法：（实际要灵活应变）

r指针右延（前进），扩大窗口（l和r指针构成的区间）
对当前窗口判断是否需要l指针前进，来满足要求。–如果前进一步不够，则加入局部循环，并进行跳出循环判断
得到阶段结果，并根据题目具体要求进行存储或者判断
破坏当前符合要求的窗口：可以是l指针前进，也可以是r指针前进。以便继续循环，得到下一个符合要求的窗口

更多例题

leetcode 567. 字符串的排列

题目描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

代码实现

不同于接下来两道题，本题给出的解法是真正意义上的「双指针做法」

只关心两个端点，通过修正l指针，保证r指针的移动合法(cnt[s2[r]] >= 0)，再判断形成的窗口是否符合要求(长度是否等于s1)

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] cnt = new int[128];
        int num = s1.length();
        for (int i = 0; i < num; ++i) {
            cnt[s1.charAt(i)]++;
        }
        int l = 0, r = 0, n = s2.length();
        while (r < n) {
            char cur = s2.charAt(r);
            cnt[cur]--;
            while (l <= r && cnt[cur] < 0) {
                cnt[s2.charAt(l)]++;
                l++;
            }
            if (r - l + 1 == num) return true;
            r++;
        }
        return false;
    }
}

剑指 Offer II 009. 乘积小于 K 的子数组

题目描述

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

代码

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0 || k == 1) return 0; 
        int l = 0, r = 0;
        int mulRes = 1, res = 0;
        while (r < nums.size()) {
            mulRes *= nums[r]; // 1、每次循环先将右指针前进一位
            while (mulRes >= k) { // 2、如果不满足条件，则调节左指针
                mulRes /= nums[l];
                l ++;
            }
            res += (r - l + 1); // 3、保存阶段结果
            r++; // 4、破坏满足条件的当前窗口，开启下一次循环
        }
        return res;
    }
};

分析

可用此模板的条件是：每次循环调节窗口时，右指针永远不用后退。
此题，由于nums中的每个数都是大于等于1的，乘积只会越来越大，满足条件。

关于res += (r - l + 1);一句
长度为n的乘积小于k的数组一共有 $\frac{n(n+1)}2$ 个同样满足条件的子数组，以nums = [5,2,6,4] k = 300为例子：

4: [5,2,6,4]
3: [5,2,6] [2,6,4]
2: [5,2] [2,6] [6,4]
1: [5] [2] [6] [4]

假设现在扫描到4(此时l = 0 r = 3)，之前的[5,2,6]已经计算过，实际增加的符合条件的子数组个数为
$\frac {4\times(4+1)}2$ - $\frac {3\times(3+1)}2 = \frac{n(n+1)}2$ - $\frac{(n-1)n}2 = n = 4$
因此此次循环答案只需增加 $n = 4$ 即可，对应到代码中即 $r$ - $l + 1$

1248. 统计「优美子数组」

问题描述

给你一个整数数组nums和一个整数k。

如果某个连续子数组中恰好有 k个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例：

1
2
3

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

代码

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        // 一旦出现连续 ，就无法先排序了
        // 但是可以考虑构造前缀和数组（原数组元素必须为正数 才能保证前缀和数组单调递增！！） 进行双指针或者二分
        int res = 0;
        int cnt = 0, n = nums.size();

        int l = 0, r = 0;
        while (r < n) {
            if (nums[r ++] & 1) cnt ++;
            if (cnt == k) { // 以上两条语句保证，进入这个判断语句，当前扫描到的数字一定是奇数
                int tmp = r;
                while (r < n && (nums[r] & 1) == 0) {
                    r ++; // 右指针右移，直到遇到下一个奇数或者越界
                } // “1 2 2 1”为例子 r++ 后 r=1，经过循环后r=3
                int rightEvenCnt = r - tmp; // 计算当前最后一个奇数右侧的偶数个数
                int leftEvenCnt = 0; // 同理，计算当前窗口第一个奇数左侧的偶数个数
                while ((nums[l] & 1) == 0) {
                    leftEvenCnt ++;
                    l ++;
                }
                // 左右的偶数均可以作为子数组的边界（也可以用奇数做边界）
                res += (rightEvenCnt + 1) * (leftEvenCnt + 1);
                l ++; // 破坏当前满足条件的窗口
                cnt --; // 由于经过最近一个while循环，此时的nums[l]一定是奇数，相应的cnt要--
            }
        }
        return res;
    }
};

剑指 Offer II 017. 含有所有字符的最短字符串

本题与1248. 统计优美子数组有异曲同工之处

题目描述：

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果s 中不存在符合条件的子字符串，则返回空字符串 ""。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例：

1
2
3

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

代码

class Solution {
public:
    string minWindow(string s, string t) {
        int need[128] = {0};
        for (auto ch : t) {
            need[ch] ++;
        }
        // 维持一个计数器，记录必须包含的有效字符数量
        int cnt = t.size(), m = INT_MAX;
        string res = "";
        int l = 0, r = 0;
        while (r < s.size()) {
            // 仅遇到t中含有的字符时 cnt减一
            if (need[s[r]] > 0) cnt --;
            need[s[r]] --;
            if (cnt == 0) {
                while (l < r && need[s[l]] < 0) {
                    need[s[l]] ++;
                    l ++;
                }
                // 得到一个有效窗口，计算此时的长度
                if (r - l + 1 < m) {
                    m = r - l + 1;
                    res = s.substr(l, r - l + 1);
                }
                // 必须在这里破坏窗口，因为经过上上面的while循环后，可保证，s[l]为t中字符
                // 此时l++一定破坏了窗口成立的条件
                need[s[l]] ++;
                l ++;
                cnt ++;
            }
            // r++这里显然并不能保证 每次r++ 都会破坏有效窗口
            // 例如 s[r]下一个字符并不在t中，r++后实际上窗口并未被破坏
            r ++;
        }
        return res;
    }
};

📔博文图谱

提及本博文的链接

单调栈/单调队列