classSolution { public: intminSubArrayLen(int target, vector<int>& nums){ int s = 0; int left = 0; int right = 0; int n = nums.size(); int ans = n + 1; for (; right < n; right ++) { s += nums[right]; // 当right固定时,left++,s减小,这就是单调性 // 从满足要求到不满足要求 while(s - nums[left] >= target) { s -= nums[left]; left ++; } if (s >= target) ans = min(ans, right - left + 1); } return ans <= n ? ans : 0; } };
classSolution { public: intlengthOfLongestSubstring(string s){ int ans = 0; int left = 0, right = 0; int n = s.size(); unordered_map<char, int> hash; for (; right < s.size(); right++) { hash[s[right]] ++; while (hash[s[right]] > 1) { hash[s[left]] --; left ++; } ans = max(ans, right - left + 1); } return ans; } };
classSolution { public: intnumSubarrayProductLessThanK(vector<int>& nums, int k){ if (k <= 1) return0; int n = nums.size(); int cheng = 1; int ans = 0; int left = 0, right = 0; for (; right < n; right ++) { cheng *= nums[right]; while (cheng >= k) { cheng /= nums[left]; left ++; } if (cheng < k) { ans += right - left + 1; } } return ans; } };
classSolution { public: intmaxSubarrayLength(vector<int>& nums, int k){ int ans = 0; int n = nums.size(); unordered_map<int, int> hash; int left = 0, right = 0; for (; right < n; right ++) { hash[nums[right]] ++; while (hash[nums[right]] > k) { hash[nums[left]] --; left ++; } ans = max(ans, right - left + 1); } return ans; } };
classSolution { public: intlongestSemiRepetitiveSubstring(string s){ int k = 0; int n = s.size(); int left = 0, right = 0; int ans = 0; for (; right < n; right ++) { if(right > 0 && s[right] == s[right - 1]) { k ++; } if (k == 2) { left ++; while (s[left] != s[left - 1]) { left ++; } k --; } ans = max(ans, right - left + 1); } return ans; } };
classSolution { public: intlongestOnes(vector<int>& nums, int k){ int n = nums.size(); int left = 0, right = 0; int ans = 0; int cur_0 = 0; for (; right < n; right ++) { cur_0 += nums[right] == 0; if (cur_0 > k) { left ++; while (nums[left - 1] != 0) left ++; cur_0 -= 1; } ans = max(ans, right - left + 1); } return ans; } };
classSolution { public: longlongcountSubarrays(vector<int>& nums, int k){ int total_max = 0; int n = nums.size(); for (int i = 0; i < n; i ++) { total_max = max(total_max, nums[i]); }
int left = 0, right = 0; int cur_cnt = 0; longlong ans = 0; for (; right < n; right ++) { if (nums[right] == total_max) { cur_cnt ++; } if (cur_cnt == k) { left ++; while (nums[left - 1] != total_max) { left ++; } cur_cnt --; } ans += left; } return ans; } };
classSolution { public: intminOperations(vector<int>& nums, int x){ // 逆向思维 // 找到一个最长的子数组,使其和为 s - x int n = nums.size(); int left = 0, right = 0; int ans = -1; int sum = 0; for (int i = 0; i < n; i ++) { sum += nums[i]; } sum = sum - x; if (sum < 0) return-1; int cur_sum = 0; for (; right < n; right ++) { cur_sum += nums[right]; while (cur_sum > sum) { cur_sum -= nums[left ++]; } if (cur_sum == sum) { ans = max(ans, right - left + 1); } } return ans == -1 ? -1 : n - ans; } };
boolcheck(){ for (auto item : hash_t) { if (hash_s[item.first] < hash_t[item.first]) returnfalse; } returntrue; }
string minWindow(string s, string t){ for (int i = 0; i < t.size(); i ++) { hash_t[t[i]] ++; } int n = s.size(); int left = 0, right = 0; int cur_len = n; string ans = ""; for (; right < n; right ++) { hash_s[s[right]] ++; if (check()) { while(hash_s[s[left]] > hash_t[s[left]]) { hash_s[s[left ++]] --; } if (cur_len >= right - left + 1) { cur_len = right - left + 1; ans = ""; for (int i = left; i <= right; i ++) { ans += s[i]; } } } } return ans; } };
string minWindow(string s, string t){ for (int i = 0; i < t.size(); i ++) { hash_t[t[i]] ++; } int n = s.size(); int left = 0, right = 0; int cur_len = n; int less = hash_t.size(); string ans = ""; for (; right < n; right ++) { hash_s[s[right]] ++; less -= hash_s[s[right]] == hash_t[s[right]]; if (less == 0) { while(hash_s[s[left]] > hash_t[s[left]]) { hash_s[s[left ++]] --; } if (cur_len >= right - left + 1) { cur_len = right - left + 1; ans = ""; for (int i = left; i <= right; i ++) { ans += s[i]; } } } } return ans; } };