力扣560题
将问题转化为寻找和为k的子数组，而不是直接在数组中寻找和为k的连续元素这样就可以使问题在一次遍历中解决。
对于每个前缀和，都检查是否存在一个早先的前缀和，使得它们的差等于k。如果存在，就找到一个和为k的子数组。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int preSum = 0;
int ans = 0;
//键：前缀和，值：前缀和出现的次数
unordered_map<int,int>record;
//初始化时为空区间，则前缀和为0，出现的次数为1
record[0] = 1;
for(const int &num:nums){
preSum += num;
if(record.count(preSum-k)){
ans += record[preSum-k];
}
++record[preSum];
}
return ans;
}
};
力扣581题 最短无序连续子数组
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int>ordered_nums(nums);
sort(ordered_nums.begin(),ordered_nums.end());
int i=0,j = nums.size()-1;
while(i<nums.size()){ //从前往后作比较
if(nums[i]==ordered_nums[i]){
i++;
}else{
break;
}
}
if(i==nums.size()){ //若遍历全部， 则原数组有序
return 0;
}
while(j>=0){ //从后往前比较
if(nums[j]==ordered_nums[j]){
j--;
}else{
break;
}
}
return j-i+1;
}
};
力扣438题 找到字符串中所有字母异位词
不管顺序，只要在窗口内的字符符合目标字符的个数即为字母异位词，所以用count1和count2来分别计数目标p和窗口内字符的个数。
如果count1=count2，则二者一致，则添加到result里。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int>result;
if(p.size()>s.size()) return result;
vector<int>count1(26,0);
vector<int>count2(26,0);
//初始化p的字符计数
for(auto c:p) count1[c-'a']++;
//初始化第一个窗口
for(int i=0;i<p.size();i++) count2[s[i]-'a']++;
if(count2==count1) result.push_back(0);
//滑动窗口
for(int i=1;i<=s.size()-p.size();i++){
count2[s[i-1]-'a']--; //移除旧左边界
count2[s[i+p.size()-1]-'a']++; //添加新右边界
if(count2==count1) result.push_back(i);
}
return result;
}
};