LeetCode.438.715.209(滑动窗口)

438.找到字符串中所有字母异位词

class Solution {
  public:
    vector<int> findAnagrams(string s, string p) {
        if (p.length() > s.length())
            return {};
        vector<int> result;
        vector<int> hashS(26, 0);
        vector<int> hashP(26, 0);
        for (int i = 0; i < p.length(); i++) {
            hashP[p[i] - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            hashS[s[i] - 'a']++;
            if (i >= p.length()) {
                hashS[s[i - p.length()] - 'a']--;
            }
            if (hashP == hashS)
                result.push_back(i - p.length() + 1);
        }
        return result;
        // 61/61 cases passed (12 ms)
        // Your runtime beats 61.38 % of cpp submissions
        // Your memory usage beats 95.66 % of cpp submissions (8.3 MB)
    }
};

713.乘积小于k的子数组

class Solution {
  public:
    int numSubarrayProductLessThanK(vector<int> &nums, int k) {
        /*int left = 0, right = 0, rightBefore = 0;
        int product = nums[left];
        int sum = 0;
        while (1) {
            if (product >= k || right == nums.size() || left == nums.size()) {
                sum += ((right - left) + 1) * (right - left) / 2;
                sum -= ((rightBefore - left) + 1) * (rightBefore - left) / 2;
                if (product >= k) {
                    product /= nums[left];
                    left++;
                    rightBefore = right;
                }
                if (right == nums.size() || left == nums.size()) {
                    break;
                }
            } else {
                right++;
                if (right < nums.size())
                    product *= nums[right];
            }
        }
        return sum;*/
        // 97/97 cases passed (64 ms)
        // Your runtime beats 70.99 % of cpp submissions
        // Your memory usage beats 38.52 % of cpp submissions (59.8 MB)
        if (k == 0 || k == 1)
            return 0;
        int l = 0;
        int prod = 1; //存储nums[l]~nums[r]的累积
        int res = 0;
        for (int r = 0; r < nums.size(); r++) {
            prod *= nums[r];
            while (prod >= k) {
                prod /= nums[l++];
            }
            res += r - l + 1; //不用rightBefore，因为每次r++都执行了一遍，所以显得简洁
        }
        return res;
        // 97/97 cases passed (72 ms)
        // Your runtime beats 36.04 % of cpp submissions
        // Your memory usage beats 99.36 % of cpp submissions (59.6 MB)
        //评论区优化过的代码，效率稍高
    }
};

209.长度最小的子数组

class Solution {
  public:
    int minSubArrayLen(int target, vector<int> &nums) {
        if (nums.empty())
            return 0;
        int left = 0, right = 0;
        int sum = nums[left];
        int minLength = INT_MAX;
        while (left < nums.size()) {
            if (sum < target) {
                if (right >= nums.size() - 1)
                    break;
                sum += nums[++right];
            } else {
                minLength = min(minLength, min(right, (int)nums.size() - 1) - left + 1);
                sum -= nums[left++];
            }
        }
        return minLength == INT_MAX ? 0 : minLength;
        // 19/19 cases passed (4 ms)
        // Your runtime beats 94.25 % of cpp submissions
        // Your memory usage beats 63.79 % of cpp submissions (10.3 MB)
    }
};