#
跟着灵茶山艾府大佬学习算法思路的day2，目标是在一个月内掌握hot100
b站链接如下：
长度最小的子数组 题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
1
2
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
思路：
暴力做法是比较好想的，只要从数组第一个元素开始，逐步往后包入新元素，包入全部元素后就停止，然后第二个元素也同理处理，最后的时间复杂度是o(n^2)（众所周知，这样总会超时）。
最优解可以被称为“蠕动法”，一开始与暴力做法类似，从第一个元素开始，窗口逐步往后包入新元素，但在包入新元素，使得数组大于target时，此时我们就不继续包入新元素了，而是将头部指针往后移动一位，使得总和变小。如果此时总和依旧大于等于target，就更新答案最小值；如总和小于target，就包入新元素。如此循环即可。
值得注意的是虽然这道题有两个循环，但left和right指针在全局内的移动次数都仅是o(n)，所以最后的时间复杂度就是o(n)。
代码：
思路1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var minSubArrayLen = function(target, nums) {
const n = nums.length;
let sum = 0;
let len = n + 1;
let left = 0;
for (let right = 0; right < n; right++) {
sum += nums[right];
while (sum - nums[left] >= target) {
// 先尝试减去左指针的值
sum -= nums[left];
left++;
}
if (sum >= target) {
// 无论是否进入while循环，if都会记录当前更优值
len = Math.min(len, right - left +1);
}
}
return (len <= n ? len : 0);
};
错误思路1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var minSubArrayLen = function(target, nums) {
const n = nums.length;
let sum = 0;
let len = n + 1;
let left = 0;
for (let right = 0; right < n; right++) {
sum += nums[right];
while (sum - nums[left] >= target) {
sum -= nums[left];
left++;
if (sum >= target) {
len = Math.min(len, right - left +1);
}
}
}
return (len <= n ? len : 0);
};
思路2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var minSubArrayLen = function(target, nums) {
const n = nums.length;
let sum = 0;
let len = n + 1;
let left = 0;
for (let right = 0; right < n; right++) {
sum += nums[right];
while (sum >= target) {
// 最大的区别：当sum >= target时，就尝试记录和缩小窗口
len = Math.min(len, right - left + 1);
// 记录当前窗口长度
sum -= nums[left]; // 缩小窗口
left++;
}
}
return len <= n ? len : 0;
};
总结：
两种思路最大的区别就是在扩展窗口后， 是先选择减去left值，还是先选择更新窗口长度。
思路1面对最优答案即为数组长度本身的特殊测试用例时，是不会进入while循环的，只能由if来更新（即错误思路1）。而对于其他长度小于数组长度本身的测试用例，即使将if判断放入while循环中，也可以通过用例。可以见得思路1面对不同的测试用例可能会带来一些边界判断的问题。
而思路2通过先更新窗口长度就避免了这一问题，在我看来思路2会更显简洁一些。
乘积小于 K 的子数组 题目描述：
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
1
2
3
4
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
示例 2：
1
2
输入：nums = [1,2,3], k = 0
输出：0
思路：
这道题和上道题不一样的地方主要有两处：一者是要求返回的是满足条件的连续子数组的数目；一者是要求乘积需要严格小于 k。
对于每个子数组的检索，依然可以采用与上一题一样的思路，先移动右端点扩大子数组乘积，直到不满足条件，就移动左端点缩小数组。
那么如何计算子数组的总数目呢？对于一个左端点为 l ，右端点为 r 的子数组而言，采用固定 r ，移动 l 的方式，所能形成的子数组个数，就是l到r的所有元素个数，即 r - l + 1。固定 r ，移动 l 的子数组计算方式便于在每次更新 r 的值时，同步计算一批新增的子数组。
如果在子数组计算时，采用固定 l , 移动 r 的方式，同样也可行，只是边界条件会复杂一些。例如常规的遍历子数组的思路是先移动右端点，在右端点持续移动，左端点还未移动过时，新的子数组其实已经源源不断地产生了。如果要等到左端点开始移动才去计算新的子数组，就会错过开始的一批子数组，这一批子数组就需要另花功夫单独进行计算。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var numSubarrayProductLessThanK = function(nums, k) {
if (k <= 1)
return 0;
const len = nums.length;
let sums = 0;
let left = 0;
let multi = 1;
let right = 0;
while (right < len) {
multi *= nums[right];
while (multi >= k) {
multi /= nums[left];
left++;
} // 保持multi结果严格小于k
sums += (right - left + 1);
right++;
}
return sums;
};
总结：
是长度最小的子数组的略微升级版，时空复杂度与上一题相同，边界条件判断和子数组总数的计算要注意。
无重复字符的最长子串 题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
1
2
3
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
示例 2:
1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：
这一题相较于之前的题目，更难一些的地方在于不同语言对于字符串的处理。而就题目本身而言，重复字符一定来自新接入的字符，则可以采用哈希表或集合记录字符的出现次数，哈希表会存储键值对，而集合则只有值，两种集合类型都可以解决这道题，因为我们只需知道目前的字符串中已有了哪些字符。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var lengthOfLongestSubstring = function(s) {
const n = s.length;
if (n <= 1) return n;
let maxLen = 0;
let left = 0;
const charSet = new Set();
for (let right = 0; right < n; right++) {
const char = s[right];
while (charSet.has(char)) {
charSet.delete(s[left]);
left++;
}// 如果字符已存在，移动左指针直到移除重复字符
charSet.add(char);
// 添加当前字符到集合
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};
总结：
对比一下这两种数据结构
1. 创建和初始化
1
2
3
4
5
6
7
// Set - 存储唯一值
const mySet = new Set();
const setFromArray = new Set([1, 2, 3, 3, 2]); // {1, 2, 3}
// Map - 存储键值对
const myMap = new Map();
const mapFromArray = new Map([['a', 1], ['b', 2]]);
2. 基本操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Set操作
const set = new Set();
set.add('apple'); // 添加值
set.has('apple'); // 检查是否存在: true
set.delete('apple'); // 删除值
set.size; // 获取大小
set.clear(); // 清空
// Map操作
const map = new Map();
map.set('name', '张三'); // 设置键值对
map.get('name'); // 获取值: '张三'
map.has('name'); // 检查键是否存在: true
map.delete('name'); // 删除键值对
map.size; // 获取大小
map.clear(); // 清空