双指针

剑指 Offer II 008. 和大于等于 target 的最短子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), sum = 0, res = INT_MAX;
        for (int i = 0, j = 0; i < n; i ++) {
            sum += nums[i];
            while (sum - nums[j] >= target) sum -= nums[j ++];
            if (sum >= target) res = min(res, i - j + 1);
        }
        return res == INT_MAX ? 0 : res;
    }
};

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

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        //已知ABC < target, 新增一位X变成ABCX, 若ABCX < target 则新增的subarray中必须满足 1.连续 2.包含X
        //所以从X向左数: X, CX, BCX, ABCX
        int n = nums.size(), product = 1, res = 0;
        for (int i = 0, j = 0; i < n; i ++ ) {
            product *= nums[i];
            while (i >= j && product >= k) product /= nums[j ++];
            res += i - j + 1;
        }
        return res;
    }
};

剑指 Offer II 010. 和为 k 的子数组 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> hash;
        vector<int> s(n + 1, 0);
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + nums[i - 1];
        hash[0] = 1; 
        int res = 0;
        // 类似双指针，哈希表存储的每个前缀和对应的个数，由于hash[0] = 1，
        // 它一定会转移到前嘴和-k为0的的位置，后面在确定其他前嘴和-当前前嘴和是否能被首前嘴和转移
        for (int i = 1; i <= n; i ++) {
            res += hash[s[i] - k];
            hash[s[i]] ++;
        }
        return res;
    }
};

剑指 Offer II 014. 字符串中的变位词 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        map<char, int> hash;    // 存储子串各个字符数量
        for (auto c: s1) hash[c] ++;    
        int tot = hash.size(), statify = 0; // tot是字符总数，statify是s2中满足要求的数量
        for (int i = 0, j = 0; i < s2.size(); i ++) {
            if (--hash[s2[i]] == 0) statify ++; 
            while (i - j + 1 > s1.size()) { // 窗口大小小于s1.size
                if (hash[s2[j]] == 0) statify --;
                hash[s2[j ++]] ++;
            }
            if (statify == tot) return true;
        }
        return false;
    }
};

剑指 Offer II 017. 含有所有字符的最短字符串 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    string minWindow(string s, string t) {
        map<char, int> hash;
        for (auto c: t) hash[c] ++;
        int tot = hash.size(), statify = 0;
        string res;
        for (int i = 0, j = 0; i < s.size(); i ++) {
            if (hash[s[i]] == 1) statify ++;
            hash[s[i]] --;
            while (hash[s[j]] < 0) hash[s[j ++]] ++;    // 注意这里是<，所以不会出现后续的不符合要求的字符顶去前面的，例如BANC，N的出现不会将B删去
            if (statify == tot) {
                if (res.empty() || res.size() > i - j + 1) {
                    res = s.substr(j, i - j + 1);
                }
            }
        }
        return res;
    }
};