文章目录

• 一、双指针
• 二、刷题
• • 1. 窗口固定大小
  • 2. 窗口大小可变

一、双指针

本质上还是双指针

二、刷题

1. 窗口固定大小

LeetCode 1343. 大小为 K 且平均值大于等于阈值的子数组数目 原题链接

class Solution {public:    int numOfSubarrays(vector<int>& arr, int k, int threshold) { int sum = 0; int ret = 0; for (int i = 0; i < k; i ++) {     sum += arr[i]; } if (sum >= threshold * k) ret ++; for (int i = k; i < arr.size(); i ++) {     sum -= arr[i - k];     sum += arr[i];     if (sum >= threshold * k) ret ++; } return ret;    }};

 
LeetCode 剑指 Offer II 015. 字符串中的所有变位词 原题链接

class Solution {public:    vector<int> findAnagrams(string s, string p) { // 变位词：字母相同，排列不同的子串 // 返回子串的起始索引 vector<int> hash(26, 0), hashZero(26, 0);  vector<int> res; if (s.length() < p.length()) return res; for (int i = 0; i < p.length(); i ++) {     hash[p[i] - 'a'] ++;     hash[s[i] - 'a'] --; } if (hash == hashZero) res.push_back(0); for (int i = p.length(); i < s.length(); i ++) {     hash[s[i] - 'a'] --;     hash[s[i - p.length()] - 'a'] ++;     if (hash == hashZero) res.push_back(i - p.length() + 1); } return res;    }};

2. 窗口大小可变

LeetCode 3. 无重复字符的最长子串 原题链接

class Solution {public:    int lengthOfLongestSubstring(string s) { vector<int> hash(256); int n = s.length(); int i = 0, j = -1; // 空串 int max = 0; while (j < n - 1) {     hash[s[++ j]] ++;     while (hash[s[j]] > 1) {  hash[s[i]] --;  i ++; }     if (max < j - i + 1) max = j - i + 1; } return max;    }};