滑動窗口、雙指針

class Solution {
public:int lengthOfLongestSubstring(string s) {//滑動窗口試一下//英文字母、數字、符號、空格,ascii 一共包含128個字符vector<int> pos(128,-1);int ans = 0;for(int i=0,j=0 ; i<s.size();i++) {//s[i]已出現過   pos[s[i]]+1 上次出現位置的下一個位置j = max(pos[s[i]]+1,j);//比較窗口的大小ans = max(ans,i-j+1);pos[s[i]] = i;}return ans;}
};

統計字符出現的次數

class Solution {
public:vector<int> findAnagrams(string s, string p) {int ssize = s.size();int psize = p.size();if(ssize < psize)return {};vector<int> ans;vector<int> count_s(26);vector<int> count_p(26);for(int i=0;i<psize;i++) {count_p[p[i]-'a']++;count_s[s[i]-'a']++;}if(count_s == count_p)ans.push_back(0);for(int i=0;i<ssize-psize;i++) {count_s[s[i]-'a']--;count_s[s[i+psize]-'a']++;if(count_s == count_p) {ans.push_back(i+1);}}return ans;}
};

前綴和、哈希表改進的前綴和

class Solution {
public:int subarraySum(vector<int>& nums, int k) {vector<int> presum(nums.size()+1);presum[0] = 0;int ans = 0;for(int i=0;i<nums.size();i++) {presum[i+1] = presum[i] + nums[i];}for(int i=1;i<=nums.size();i++) {for(int j=0;j<i;j++) {if(presum[i]-presum[j] == k)ans++;}}return ans;}
};

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();unordered_map<int,int> presum;presum[0]=1;int ans = 0,sum_i = 0;for(int i=0;i<n;i++) {sum_i += nums[i];int sum_j = sum_i-k;if(presum.find(sum_j) != presum.end())ans += presum[sum_j];presum[sum_i]++;}return ans;}
};