滑动窗口算法
209. 长度最小的子数组
题目：给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int len = INT_MAX;
int sum = 0;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right];
while (sum >= target) {
len = min(len, right - left + 1);
sum -= nums[left++];
}
}
return len == INT_MAX ? 0 : len;
}
};
算法思路：
- 暴力枚举：两层循环枚举所有情况，时间复杂度 O(N^3)。优化后可达 O(N^2)。
- 同向双指针（滑动窗口）：利用单调性，当
sum >= target时，无需继续移动右指针，而是收缩左指针。时间复杂度优化为 O(N)。
3. 无重复字符的最长子串
题目：给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0};
int n = s.length();
int ret = ;
( left = , right = ; right < n; right++) {
hash[s[right]]++;
(hash[s[right]] > ) hash[s[left++]]--;
ret = (ret, right - left + );
}
ret;
}
};
