LeetCode算法入门（第五十二天）
滑动窗口
438.找到字符串中所有字母异位词
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if (sLen < pLen) {
return vector<int>();
}
vector<int> ans;
vector<int> sCount(26);
vector<int> pCount(26);
for (int i = 0; i < pLen; ++i) {
++sCount[s[i] - 'a'];
++pCount[p[i] - 'a'];
}
//初始化窗口内的字符词频相同
if (sCount == pCount) {
ans.emplace_back(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s[i] - 'a']; //滑动窗口左移
++sCount[s[i + pLen] - 'a'];
if (sCount == pCount) {
ans.emplace_back(i + 1);
}
}
return ans;
}
};
713.乘积小于K的子数组
题目要求是连续的子数组。
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k <= 1){
return 0;
}
int first = 0, ans = 1, count = 0;
for(int right = 0; right < nums.size(); right++){
ans *= nums[right];
//大于K时，需将需除去左值，并且左指针++
while(ans >= k){
ans /= nums[first];
first++;
}
count += right - first +1; //每次的子数组个数为当前区间长度+1
}
return count;
}
};
209.长度最小的子数组
长度最小的连续子数组，所以初始化子数组长度时用INT_MAX，那样每次都可以用min函数来取当前最小长度的子数组。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= target) {
ans = min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == INT_MAX ? 0 : ans;
}
};
