滑动窗口438

Question

老师好，关于滑动窗口438题。我想的是用两个数组，一个放p串的词频，一个放子串词频。大致思路是对的，但对于滑动窗口l, r细节的代码我尝试了很久也没写出来，我本来是想用while循环来做，然后看leetcode解析发现基本都是for循环，这题只能用for循环吗。能提供下您的代码和思路吗？

Answer 1

liuyubobobo 2024-01-20 09:41:18

所有的 while 循环和 for 循环之间一定能互相转换。

初始条件
while(结束条件){
    // 循环体
    循环变量变化
}

等价于：

for(初始条件; 结束条件; 循环变量变化){
    // 循环体
   
}

在需要的时候，初始条件，结束条件，循环变量的变化，都可以为空；

也正因为如此，for 循环更适合于“规则的循环过程”，而 while 循环更加灵活。但这两种循环形式肯定可以互换。

比如我这里的 while 代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0438-Find-All-Anagrams-in-a-String/cpp-0438/main.cpp

改写成 for 代码如下：（请仔细体会这个代码变化和上面的 for 和 while 等价关系之间的对应。）

class Solution {

public:
    vector<int> findAnagrams(string s, string p) {
        
        vector<int> res;
        if(s.size() < p.size())
            return res;
        
        assert(p.size() > 0);
        vector<int> freq_p(26, 0);
        for(char c: p)
            freq_p[c - 'a'] += 1;
        
        vector<int> freq_s(26, 0);
        for(int l = 0, r = -1; r + 1 < s.size(); ){
            r ++;
            freq_s[s[r] - 'a'] ++;
            if(r - l + 1 > p.size())
                freq_s[s[l++] - 'a'] --;
            if(r - l + 1 == p.size() && same(freq_s, freq_p))
                res.push_back(l);
        }
        return res;
    }
    
private:
    bool same(const vector<int>& freq_s, const vector<int>& freq_p){
        for(int i = 0 ; i < 26; i ++)
            if(freq_s[i] != freq_p[i])
                return false;
        return true;
    }
};

事实上，到底是 for 循环还是 while 循环完全不重要。重要的是你的逻辑是怎样的。在逻辑清晰的基础上，怎么写方便怎么写来。面试的时候（实际工作的时候）几乎不会有人 care 你的循环到底是 for 还是 while 的，关键是逻辑是否正确清晰。

继续加油！：）