刷题 双指针 滑动窗口

学会内部字母处理函数的使用

class Solution {
public:bool isPalindrome(string s) {int left = 0, right = s.size() - 1;while (left <= right) {// 处理左边字符if (!isalnum(s[left])) {++left;continue;}// 处理右边字符if (!isalnum(s[right])) {--right;continue;}// 忽略大小写后比较字符if (tolower(s[left]) != tolower(s[right])) {return false;}++left;--right;}return true;}
};

class Solution {
public:// 双指针bool isSubsequence(string s, string t) {int i = 0;for (int j = 0; i < s.size() && j < t.size(); ++j) {if (s[i] == t[j]) {++i;}}return (i == s.size());}
};

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int left = 0, right = numbers.size() - 1;while(left < right) {int sum = numbers[left] + numbers[right];if (sum > target) --right;else if (sum < target) ++left;else return {left + 1, right + 1};}return {-1, -1};}
};

class Solution {
public:int maxArea(vector<int>& height) {int ans = 0, n = height.size();for (int l = 0, r = n - 1; l < r;) {ans = max(ans, min(height[l], height[r]) * (r - l));// 移动较长边：面积一定缩小// 移动较短边: 面积有可能变大if (height[l] < height[r]) {++l; } else {--r;}}return ans; }
};

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;int n = nums.size();sort(nums.begin(), nums.end());for (int i = 0; i < n - 2; ++i) {while (i > 0 && i < n - 2 && nums[i] == nums[i - 1]) {++i;}if (nums[i] > 0) {break;}for (int j = i + 1, k = n - 1; j < k;) {if (nums[k] < 0) {break;}int sum = nums[i] + nums[j] + nums[k];if (sum < 0) {++j;} else if (sum > 0) {--k;} else {result.push_back({nums[i], nums[j], nums[k]});++j;--k;while (j < k && nums[j] == nums[j - 1]) {++j;}// while (k > j && nums[k] == nums[k - 1]) {//     --k;// }}}}return result;}
};

class Solution {
public:// 题目要求：总和大于等于 target 的长度最小的 子数组// 当找到窗口总和 大于等于 target，记录窗口宽度，再从左侧缩小窗口直至小于 targetint minSubArrayLen(int target, vector<int>& nums) {int sum = 0;size_t ans = INT_MAX;for (size_t left = 0, right = 0; right < nums.size(); ++right) {sum += nums[right];while (sum >= target) {ans = min(ans, right - left + 1);sum -= nums[left];++left;}}return ((ans == INT_MAX) ? 0 : ans);}
};

class Solution {
public:int lengthOfLongestSubstring(string s) {size_t ans = 0;array<char, 128> hash = {0};    // 包含所有 ASCII 码for (size_t left = 0, right = 0; right < s.size(); ++right) {while (hash[s[right]] == 1) {--hash[s[left]];++left;}++hash[s[right]];ans = max(ans, right - left + 1);}return ans;}
};

class Solution {
public:// 题目的特别之处：words 中所有字符串的长度都相同// 那我们是不是可以先获得子串的长度// 暴力解法: 根据 子串长度 * 单词表的大小 截取来做匹配// 复杂度: O(n * m)// 如何优化？分组滑动窗口 --> 分成 m 组// eg. barfoothefoobarman//      i = 0   [bar][foo][the][foo][bar][man]//      i = 1   b[arf][oot][hef][oob][arm]an//      i = 2   ba[rfo][oth][efo][oba][rma]nvector<int> findSubstring(string s, vector<string>& words) {size_t n = words.size(), m = words[0].size(), total_len = m * n;if (total_len > s.size()) return vector<int>{};unordered_map<string, int> word_count;vector<int> ans;for (auto& word : words) {word_count[word]++;}for (size_t i = 0; i < m; ++i) {    unordered_map<string, int> window_count;int words_used = 0;for (size_t left = i, right = i; right + m <= s.size(); right += m) {string word = s.substr(right, m);if (word_count.find(word) != word_count.end()) {// 单词存在window_count[word]++;words_used++;// 检测单词频率是否超过限制while (window_count[word] > word_count[word]) {window_count[s.substr(left, m)]--;words_used--;left += m;}if (words_used == n) {ans.push_back(left);}} else {// 出现不存在的单词，直接清空重新开始即可window_count.clear();words_used = 0;left = right + m;   // 将left移动到下一个位置}}}return ans;}
};

// 用时：35:57
// 主要 bug: 把 win_char_counts[s[left]]等 写成 win_char_counts[left]
// 超出内存限制：把每次记录的 ans = s.substr(left, min_len) 改成记录 start_idx
//              最终输出结果的时候才执行 substr，减少内存操作class Solution {
public:string minWindow(string s, string t) {if (s.size() < t.size()) return "";int min_len = INT_MAX, start_idx = 0;unordered_map<char, int> t_char_counts;for (auto& ch : t) {t_char_counts[ch]++;}size_t covered_count = 0;   // 记录已经覆盖多少t中字符了unordered_map<char, int> win_char_counts;for (size_t left = 0, right = 0; right < s.size(); right++) {if (t_char_counts.find(s[right]) != t_char_counts.end()) {// 当前字符是在 t 中存在，更新出现的频次win_char_counts[s[right]]++;if (win_char_counts[s[right]] <= t_char_counts[s[right]]) {// 只有当频次小于等于 t 中出现的频次时才更新 覆盖字符数// 因为多了的话也用不上，最多只用得上 t_char_counts[right] 这么多covered_count++;}while (covered_count == t.size()) {   // 为什么是while，因为每次更新left之后都需要更新 min_len 和 ans// 找到覆盖子串，更新结果并移动 left 直至恰好不满足if (right - left + 1 < min_len) {min_len = right - left + 1;start_idx = left;}// 移动 leftif (t_char_counts.find(s[left]) != t_char_counts.end()) {if (win_char_counts[s[left]] <= t_char_counts[s[left]]) {covered_count--;}win_char_counts[s[left]]--;}++left;}}}return ((min_len == INT_MAX) ? "" : s.substr(start_idx, min_len));}
};