1. 长度最小的子数组
1.1 解题思路和方法
1.1.1 暴力做法
- 对于每个元素，可以枚举其左端点，不断向右扩展，直到
>=target； - 同理，对于每个元素，可以枚举其右端点，不断向左扩展，直到
>=target。
点击查看代码
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 暴力做法int n = nums.size();int min_len = INT_MAX;for (int i = 0; i < n; ++i) {int s = 0;for (int j = i; j < n; ++j) {s += nums[j];if (s >= target) {min_len = min(min_len, j - i + 1);break;} }}return min_len == INT_MAX ? 0: min_len;}
};
1.1.2 滑动窗口
由于数组中的元素都是正数，因此我们可以枚举右端点，考虑不断缩短左端点。
例如，[2 3 1 2 4 3]
对于 target = 7，我们通过暴力做法不断枚举右端点，我们知道以4为右端点的>= 7的子数组是[1 2 4]。
紧接着，暴力做法继续枚举以3为右端点的子数组。这个时候[1 2 4 3]一定是满足条件的，因为数组中的元素都是正数，我们是想知道缩短左端点后[2 4 3],[4 3]这些子数组是不是仍然满足条件呢？
所以通过暴力做法，就有了不断缩小子数组的左端点（滑动窗口）的思路。
1.1.2（1） 第1种写法
点击查看代码
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 暴力做法int n = nums.size();int min_len = INT_MAX;int s = 0;int left = 0;for (int i = 0; i < n; ++i) { // i是右端点s += nums[i]; // 枚举右端点，就要将其加到s中,假如此时右端点是3// 这里为什么 while 没有判断 left <= right?// 因为如果 left == right s = 0，而target是正数while (s - nums[left] >= target) { // nums[left] = 1, [1 2 4 3]s -= nums[left];++left;} // 循环结束是 [4 3]if (s >= target) {min_len = min(min_len, i - left + 1);}}return min_len == INT_MAX ? 0: min_len;}
};
1.1.2（2）第2种写法（好理解）
点击查看代码
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 暴力做法int n = nums.size();int min_len = INT_MAX;int s = 0;int left = 0;for (int i = 0; i < n; ++i) { // i是右端点s += nums[i]; while (s >= target) {min_len = min(min_len, i - left + 1);s -= nums[left];++left;}}return min_len == INT_MAX ? 0: min_len;}
};
- 时间复杂度：$$O(n)$$
- 空间复杂度：$$O(1)$$
1.2 小结
双指针的应用场景：单调性（在
left移动时，子数组的和是在不断变小的。while条件从满足要求->不满足要求）。
2. 乘积小于K的子数组
2.1 解题思路
这道题可以沿用上一题的思路，原因是数组中的元素全是正数。
唯一不同之处是这道题要求返回连续子数组的数目。
以[10 5 2 6]为例，当以2为右端点时，5为左端点时，子数组的数目应该是[5 2]和[2]，因此相应的公式应该是right - left + 1。
注意：可以这样理解，如果说[l,r]是满足要求的，那么[l, r],[l + 1, r]...[r, r]都是满足要求的，且数目是r - l + 1个。
点击查看代码
class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {if (k == 0 || k == 1) {return 0;} // 由于nums都是正整数，所以当k==0或1时要直接返回int n = nums.size();int s = 1;int ans = 0, left = 0;for (int i = 0; i < n; ++i) {s *= nums[i];while (s >= k) { s /= nums[left];++left;}ans += i - left + 1;}return ans;}
};
- 时间复杂度：$$O(n)$$
- 空间复杂度：$$O(1)$$
3. 无重复字符的最长子串
点击查看代码
class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();int max_len = 0, left = 0;unordered_map<char, int> hash_table;for (int i = 0; i < n; ++i) {if (hash_table.contains(s[i])) {hash_table[s[i]]++;while (left <= i && hash_table[s[i]] > 1) {hash_table[s[left]]--;/*if (hash_table[s[left]] == 0) {hash_table.erase(s[left]);}*/++left;}} else {hash_table[s[i]] = 1;}max_len = max(max_len, i - left + 1);}return max_len;}
};