LC567.字符串的排列

思路：滑动窗口（双指针）

• 可以常规滑动窗口做，比较简单，但是空间成本比较大。
• 维护一个账本debt[26]，账本里面的26个项目对应26个字母
• s1中的所有账目都是欠的钱
• ++debt[s2[right] -'a'],right指向的位置可以还钱，但是如果多还了，就要一直右移左指针，直到没有多还为止（确保left到right范围内的字母都在s1中），如果长度和s1相同，那么就是子字符串。

代码：

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        // s1可以看成一个欠账本，里面一共有26项
        // s2可以看成一个还钱的账本，也是一共26项
        vector<int> debt(26, 0);
        int len_s1 = s1.size(), len_s2 = s2.size();
        for (int i = 0; i < len_s1; ++i) {
            debt[s1[i] - 'a']--;
        }
        for (int left = 0, right = 0; right < len_s2; ++right) {
            // right 所在的位置是还钱的
            ++debt[s2[right] - 'a'];
            while (debt[s2[right] - 'a'] > 0) {
                // 如果多还了钱，那么要把之前多还的欠回去
                // 确保left - right范围内都是s1中出现过的
                --debt[s2[left++] - 'a'];
            }
            // 如果已经还的钱的数量，和一开始欠的数量相同，那么就存在子字符串
            if (right - left + 1 == len_s1) {
                return true;
            }
        }
        return false;
    }
};