数组：排序

0031. 下一个排列 (opens new window)

题目

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

解析

1. 从后向前找到第一个正序数 k；
2. 从后向前找到第一个比 k 大的数 t；
3. 交换 k 和 t，并将原 k 位置后面的数字逆序。

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while (k > 0 && nums[k - 1] >= nums[k]) k--;
        if (k <= 0) {
            reverse(nums.begin(), nums.end());
        } else {
            int t = nums.size() - 1;
            while (nums[t] <= nums[k - 1]) t--;
            swap(nums[t], nums[k - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};

0075. 颜色分类 (opens new window)

题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

解析

使用三指针 i、j、k，要保证 [0, i - 1] 部分全部是 0；[i, j - 1] 部分全部是 1；[k + 1，n - 1] 部分全部是 2；

我们使用 j 这个指针对数组遍历，那么当 j > k 时就完成了对数组的排序。

代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i = 0, j = 0, k = nums.size() - 1;
        while (j <= k) {
            if (nums[j] == 0) swap(nums[i++], nums[j++]);
            else if (nums[j] == 2) swap(nums[j], nums[k--]);
            else j++;
        }
    }
};

0088. 合并两个有序数组 (opens new window)

题目

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

解析

逆序双指针，从后向前遍历两个数组，选取大的元素从后向前赋值。

代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int idx = m + n - 1;
        int i = m - 1, j = n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) nums1[idx--] = nums1[i--];
            else nums1[idx--] = nums2[j--];
        }
        while (j >= 0) nums1[idx--] = nums2[j--];
    }
};

0164. 最大间距 (opens new window)

题目

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

解析

这里用桶排序 Bucket Sort 来做。

首先找出数组的最大值 max 和最小值 min，然后要确定每个桶的容量 $size$，即为 $(\max - \min)/n + 1$；再确定桶的个数 $cnt$，即为 $(\max - \min) / size + 1$；之后将所有数据入桶，每个桶维护一个桶内的最大值和最小值。

易证，数组排序后相邻元素最大差值一定在不同桶之间，只需遍历所有非空桶，计算后面桶的最小值与前面桶的最大值的差即可。

代码

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) return 0;

        int min_num = *min_element(nums.begin(), nums.end());
        int max_num = *max_element(nums.begin(), nums.end());

        int n = nums.size();
        int size = (max_num - min_num) / n + 1;
        int cnt = (max_num - min_num) / size + 1;

        vector<int> bucket_max(cnt, INT_MIN);
        vector<int> bucket_min(cnt, INT_MAX);

        for (int i = 0; i < n; i ++) {
            int idx = (nums[i] - min_num) / size;
            bucket_max[idx] = max(bucket_max[idx], nums[i]);
            bucket_min[idx] = min(bucket_min[idx], nums[i]);
        }

        int ans = 0, pre_idx = 0;
        for (int i = 1; i < cnt; i ++) {
            if (bucket_min[i] == INT_MAX || bucket_max[pre_idx] == INT_MIN) continue;
            ans = max(ans, bucket_min[i] - bucket_max[pre_idx]);
            pre_idx = i;
        }
        return ans;
    }
};

0205. 同构字符串 (opens new window)

题目

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。

解析

本题的思想是将 s 和 t 转换成一个新的规则表示，如：s = "abb"，t = "egg"，则 s 和 t 都可以表示成 011 这种形式。

通过这样统一的规则转换即可判断两字符串是否同构。

代码

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> m1(256, -1);
        vector<int> m2(256, -1);
        for (int i = 0; i < s.length(); i ++) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] = m2[t[i]] = t[i];
        }
        return true;
    }
};

0215. 数组中的第K个最大元素 (opens new window)

题目

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解析

方法一：快速选择，由快速排序改进而来，由于快速排序每次划分必定可以确定一个主元的位置，这样不断缩小划分的范围，直到遇到第 k 大的主元返回，时间复杂度 $O(n)$，空间复杂度 $O(1)$。

方法二：使用一个容量为 k 的小根堆，遍历数组结束时返回 top 即可，时间复杂度 $O(nlogk)$，空间复杂度 $O(k)$。

代码

方法一：快速选择

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (true) {
            int pos = partition(nums, left, right);
            if (pos + 1 == k) {
                return nums[pos];
            } else if (pos + 1 > k) {
                right = pos - 1;
            } else {
                left = pos + 1;
            }
        }
    }

    int partition(vector<int>& nums, int left, int right) {
        random_swap(nums, left, right);
        int privot = nums[left];
        int l = left + 1, r = right;
        while (true) {
            while (l <= r && nums[l] >= privot) l ++;
            while (l <= r && nums[r] <= privot) r --;
            if (l > r) break;
            swap(nums[l], nums[r]);
        }
        swap(nums[left], nums[r]);
        return r;
    }

    void random_swap(vector<int>& nums, int left, int right) {
        srand((unsigned)time(NULL));
        int idx = rand() % (right - left + 1) + left;
        swap(nums[left], nums[idx]);
    }
};

方法二：小根堆

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> s;
        for(int i = 0; i < k; i ++){
            s.push(nums[i]);
        }
        for(int i = k; i < nums.size(); i ++){
            if(nums[i] > s.top()){
                s.push(nums[i]);
                s.pop();
            }
        }
        return s.top();
    }
};

0274. H 指数 (opens new window)

题目

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

解析

先排序，然后遍历数组，更新 h 值（计算当前值与剩余数量的最小值）。

代码

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());

        int ans = 0, n = citations.size();
        for (int i = 0; i < n; i ++) {
            ans = max(ans, min(citations[i], n - i));
        }
        return ans;
    }
};

0283. 移动零 (opens new window)

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

解析

使用一个 idx 指针，指向非零元素的最后一个位置，遍历数组，当遇到非零数字时，将其移动到 idx 上，并把 idx 后移。

当遍历结束后，把 idx 后面的位置全部置为 0 即可。

代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int idx = 0;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] != 0) {
                nums[idx++] = nums[i];
            }
        }
        while (idx < nums.size()) {
            nums[idx++] = 0;
        }
    }
};

0287. 寻找重复数 (opens new window)

题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数 ，找出这个重复的数 。

解析

本题可以转换为已知一个有环链表，求出环的入口，解法及推导见：0142. 环形链表 II

代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

0299. 猜数字游戏 (opens new window)

题目

请写出一个根据秘密数字和朋友的猜测数返回提示的函数，返回字符串的格式为 xAyB ，x 和 y 都是数字，A 表示公牛，用 B 表示奶牛。

• xA 表示有 x 位数字出现在秘密数字中，且位置都与秘密数字一致。
• yB 表示有 y 位数字出现在秘密数字中，但位置与秘密数字不一致。

请注意秘密数字和朋友的猜测数都可能含有重复数字，每位数字只能统计一次。

解析

使用一个数组记录 secret 和 guess 中出现的数字，其中 secret 会对其中的数字“加一”，guess 会对其中的数字“减一”，这样就可以进行一一匹配，统计配对的数量。

代码

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        vector<int> cnt(10, 0);
        for (int i = 0; i < secret.length(); i ++) {
            if (secret[i] == guess[i]) {
                bulls ++;
                continue;
            }
            if (cnt[secret[i] - '0'] ++ < 0) cows ++;
            if (cnt[guess[i] - '0'] -- > 0) cows ++;
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

0300. 最长递增子序列 (opens new window)

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

解析

状态设计思想：着眼于某个上升子序列的结尾的元素，如果已经得到的上升子序列的结尾的数越小，那么遍历的时候后面接上一个数，会有更大的可能构成一个长度更长的上升子序列。既然结尾越小越好，我们可以记录在长度固定的情况下，结尾最小的那个元素的数值。

这样可以定义 $tails[i]$ 为长度为 i + 1 的所有上升子序列的结尾的最小值，具体算法如下：

1. 在遍历数组 nums 的过程中，看到一个新数 num，如果这个数严格大于有序数组 tails 的最后一个元素，就把 num 放在有序数组 tails 的后面，否则进入第 2 点；
2. 在有序数组 tails 中查找第 1 个等于大于 num 的那个数，试图让它变小；
   • 如果有序数组 tails 中存在 等于 num 的元素，什么都不做，因为以 num 结尾的最短的「上升子序列」已经存在；
   • 如果有序数组 tails 中存在 大于 num 的元素，找到第 1 个，让它变小，这样我们就找到了一个结尾更小的相同长度的上升子序列。

最后我们只需要返回 tails 数组的长度即可。

其中第 2 步可以用二分搜索确定更新的位置，算法的整体时间复杂度为 $O(nlogn)$

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;

        vector<int> tails;
        tails.push_back(nums[0]);
        for (int i = 1; i < n; i ++) {
            if (nums[i] > tails.back()) {
                tails.push_back(nums[i]);
            } else {
                int l = 0, r = tails.size() - 1;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (tails[mid] < nums[i]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                tails[l] = nums[i];
            }
        }
        return tails.size();
    }
};

0334. 递增的三元子序列 (opens new window)

题目

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k，使得 nums[i] < nums[j] < nums[k]，返回 true；否则，返回 false。

解析

核心思想是，使用两个变量 min 和 second_min，记录递增子序列的前二个数，当遍历时遇到比第二个数大的元素时，说明找到了递增子序列。

注意

当遇到一个 num 比 min 小时，为什么可以直接替换 min ？

本题目标是确定是否存在递增子序列，因此只需要保证第三个数的判断条件正确即可。

直接替换 min，深层含义是存在一个 mid_min，其值在 min 和 second_min 之间，并不会影响我们对第三个数的判断，而且这相当于帮我们扩大了之后出现的 second_min 的可选择范围，进而扩大了之后出现的 target 的可选择范围。

代码

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int min = INT_MAX, second_min = INT_MAX;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] <= min) {
                min = nums[i];
            } else if (nums[i] <= second_min) {
                second_min = nums[i];
            } else {
                return true;
            }
        }
        return false;
    }
};

0347. 前 K 个高频元素 (opens new window)

题目

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

解析

方法一：使用一个容量为 k 的小根堆，根据元素出现的次数排序，遍历数组结束时返回堆中元素即可，时间复杂度 $O(nlogk)$，空间复杂度 $O(k)$。

方法二：桶排序，桶的划分标准为元素出现的次数，只需按出现次数降序，返回 k 个元素即可，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

代码

方法一：小根堆

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int i = 0; i < nums.size(); i ++) {
            freq[nums[i]] ++;
        }

        // 小根堆，pair 的第一个元素代表数字出现的次数，第二个元素代表数字的值
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

        unordered_map<int, int>::iterator iter;
        for (iter = freq.begin(); iter != freq.end(); iter ++) {
            q.push(pair<int, int>{iter->second, iter->first});
            if (q.size() > k) q.pop();
        }

        vector<int> ans;
        for (int i = 0; i < k; i ++) {
            ans.push_back(q.top().second);
            q.pop();
        }
        return ans;
    }
};

方法二：桶排序

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int i = 0; i < nums.size(); i ++) {
            freq[nums[i]] ++;
        }

        unordered_map<int, vector<int>> buckets;
        
        unordered_map<int, int>::iterator iter;
        for (iter = freq.begin(); iter != freq.end(); iter ++) {
            buckets[iter->second].push_back(iter->first);
        }

        vector<int> ans;
        for (int i = nums.size(); i >= 0; i --) {
            if (buckets.find(i) == buckets.end()) continue;
            ans.insert(ans.end(), buckets[i].begin(), buckets[i].end());
            if (ans.size() >= k) break;
        }
        return ans;
    }
};

0358. K 距离间隔重排字符串 (opens new window)

题目

给你一个非空的字符串 s 和一个整数 k，你要将这个字符串中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离至少为 k。

所有输入的字符串都由小写字母组成，如果找不到距离至少为 k 的重排结果，请返回一个空字符串 ""。

解析

使用一个数组记录每个字母出现的次数，并维护一个记录每个字母可插入的最近位置的数组，每次选取字母的原则如下：

1. 优先选取出现次数较多的字母
2. 插入间隔最小为 k

代码

class Solution {
public:
    string rearrangeString(string s, int k) {
        vector<int> cnt(26);
        vector<int> valid(26);

        for (int i = 0; i < s.length(); i ++) {
            cnt[s[i] - 'a'] ++;
        }

        string ans = "";
        for (int i = 0; i < s.length(); i ++) {
            int next = findNext(cnt, valid, i);
            if (next == -1) return "";
            ans += ('a' + next);
            cnt[next] --;
            valid[next] = i + k;
        }
        return ans;
    }

    int findNext(vector<int> cnt, vector<int> valid, int idx) {
        int max_cnt = 0, ret = -1;
        for (int i = 0; i < cnt.size(); i ++) {
            if (cnt[i] > max_cnt && idx >= valid[i]) {
                ret = i;
                max_cnt = cnt[i];
            }
        }
        return ret;
    }
};

0383. 赎金信 (opens new window)

题目

给定一个赎金信 (ransom) 字符串和一个杂志（magazine）字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true；否则返回 false。

解析

统计 magazine 中每个字符的数量，遍历 ransom，若字符数量不够则返回 false，遍历结束返回 true。

代码

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> cnt(26, 0);
        for (int i = 0; i < magazine.length(); i ++) {
            cnt[magazine[i] - 'a'] ++;
        }
        for (int i = 0; i < ransomNote.length(); i ++) {
            if (--cnt[ransomNote[i] - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

0387. 字符串中的第一个唯一字符 (opens new window)

题目

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

解析

记录每一个字符出现的次数，之后遍历字符串，找到第一个出现次数为 1 的字符返回。

代码

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> cnt(26, 0);
        for (int i = 0; i < s.length(); i ++) {
            cnt[s[i] - 'a'] ++;
        }
        for (int i = 0; i < s.length(); i ++) {
            if (cnt[s[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
};

0406. 根据身高重建队列 (opens new window)

题目

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

解析

首先对输入数组预处理，按照 h 降序，k 升序排列。

之后进行插入排序，遍历数组，每个元素插入位置为 $k_i$，由于原数组已按 h 排序，因此后面元素的插入不会影响当前元素 $k_i$ 的正确性。

代码

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);

        vector<vector<int>> ans;
        for (int i = 0; i < people.size(); i ++) {
            ans.insert(ans.begin() + people[i][1], people[i]);
        }
        return ans;
    }

    static bool cmp(vector<int> a, vector<int> b) {
        return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    }
};

0451. 根据字符出现频率排序 (opens new window)

题目

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

解析

桶排序，思路与 0347. 前 K 个高频元素 相同。

代码

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> freq;
        for (int i = 0; i < s.length(); i ++) {
            freq[s[i]] ++;
        }

        unordered_map<int, vector<char>> buckets;
        
        unordered_map<char, int>::iterator iter;
        for (iter = freq.begin(); iter != freq.end(); iter ++) {
            buckets[iter->second].push_back(iter->first);
        }

        string ans = "";
        for (int i = s.length(); i >= 0; i --) {
            if (buckets.find(i) == buckets.end()) continue;
            for (int j = 0; j < buckets[i].size(); j ++) {
                for (int k = 0; k < i; k ++) {
                    ans += buckets[i][j];
                }
            }
        }
        return ans;
    }
};

0462. 最少移动次数使数组元素相等 II (opens new window)

题目

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加 1 或减 1。 您可以假设数组的长度最多为 10000。

解析

本题的实质是找出数组的中位数，计算每个元素与中位数的差值即可。

寻找中位数的方法可以通过排序，也可以通过快速选择算法，参考 0215. 数组中的第K个最大元素。

代码

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int ans = 0;
        int median = nums[nums.size() / 2];
        for (int i = 0; i < nums.size(); i ++) {
            ans += abs(nums[i] - median);
        }

        return ans;
    }
};

0467. 环绕字符串中唯一的子字符串 (opens new window)

题目

把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

现在我们有了另一个字符串 p。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p，你需要输出字符串 s 中 p 的不同的非空子串的数目。

解析

只需求出 p 中以每个字符结尾的最长连续子串的长度即可。统计所有以每个字符结尾的最长连续子串的长度，就是唯一相等子串的个数。

代码

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector<int> cnt(26, 0);
        int curMax = 0 ;
        for (int i = 0; i < p.length(); i ++) {
            if (i > 0 && ((p[i] - p[i - 1] - 1) % 26 == 0)) {
                curMax ++;
            } else {
                curMax = 1;
            }
            cnt[p[i] - 'a'] = max(curMax, cnt[p[i] - 'a']);
        }
        return accumulate(cnt.begin(), cnt.end(), 0);
    }
};

0493. 翻转对 (opens new window)

题目

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

解析

归并排序，在归并过程中统计两个有序子数组间的逆序对，累加结果。

代码

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if (nums.size() < 2) return 0;
        return reversePairsHelper(nums, 0, nums.size() - 1);
    }

    int reversePairsHelper(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;

        int mid = left + (right - left) / 2;
        int n1 = reversePairsHelper(nums, left, mid);
        int n2 = reversePairsHelper(nums, mid + 1, right);

        int ans = n1 + n2;

        // 统计翻转对个数
        int i = left, j = mid + 1;
        while (i <= mid) {
            while (j <= right && (long long)nums[i] > 2 * (long long)nums[j]) j ++;
            ans += (j - mid - 1);
            i ++;
        }

        // 合并左右两个子数组
        vector<int> merge(right - left + 1);
        int p1 = left, p2 = mid + 1;
        int pos = 0;
        while (p1 <= mid && p2 <= right) {
            if (nums[p1] <= nums[p2]) {
                merge[pos ++] = nums[p1 ++];
            } else {
                merge[pos ++] = nums[p2 ++];
            }
        }
        while (p1 <= mid) merge[pos ++] = nums[p1 ++];
        while (p2 <= right) merge[pos ++] = nums[p2 ++];

        // 将排序后的数组更新至原数组
        for (int i = 0; i < merge.size(); i ++) {
            nums[i + left] = merge[i];
        }

        return ans;
    }
};

0567. 字符串的排列 (opens new window)

题目

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

解析

本题是 0076. 最小覆盖子串 的简化版，这里只需要判断子串长度与 s1 是否相等即可。

代码

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> cnt(128);
        for (int i = 0; i < s1.length(); i ++) {
            cnt[s1[i]]++;
        }
        int total = s1.length();
        for (int i = 0, j = 0; i < s2.length(); i ++) {
            if (cnt[s2[i]]-- > 0) total--;
            while (total == 0) {
                if (i - j + 1 == s1.length()) {
                    return true;
                }
                if (++cnt[s2[j++]] > 0) total++;
            }
        }
        return false;
    }
};