【12.22】转行小白历险记-算法01

不会算法的小白不是好小白，可恶还有什么可以难倒我这个美女的，不做花瓶第一天！

一、长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

1.思路

滑动窗口法：把数组的区间，假设成为两个指针，先后移动两个指针

我们先读懂题目，这个很重要，不过我现在读的不是很懂，没事美女有弱点可以理解

2.辅助理解的例子（没办法罗，思路不过脑子只能解析一下）

let transactions = [1, 2, 3, 4, 5];

目标是找到一个连续的子数组，其元素总和至少为 9

let target = 9;
let result = minSubArrayLen(target, transactions);

1.初始设置

transactions = [1, 2, 3, 4, 5]
target = 9
start = 0, end = 0
sum = 0
ans = Infinity

2.迭代过程

1. 第一轮迭代: end = 0

   • sum = 1 (1)
   • sum < target (9)，所以 end++。

2. 第二轮迭代: end = 1

   • sum = 3 (1 + 2)
   • sum < target，所以 end++。

3. 第三轮迭代: end = 2

   • sum = 6 (1 + 2 + 3)
   • sum < target，所以 end++。

4. 第四轮迭代: end = 3

   • sum = 10 (1 + 2 + 3 + 4)
   • sum >= target:
     • Math.min(ans, end - start + 1) -> Math.min(Infinity, 4 - 0 + 1) -> ans = 4
     • sum -= nums[start]，start++ -> sum = 9 (2 + 3 + 4), start = 1

5. 第五轮迭代: end = 3

   • sum = 9 (2 + 3 + 4)
   • sum >= target:
     • Math.min(ans, end - start + 1) -> Math.min(4, 4 - 1 + 1) -> ans = 3
     • sum -= nums[start]，start++ -> sum = 7 (3 + 4), start = 2

6. 接下来的迭代

   • end 继续增加，但不再找到总和大于等于 target 的更短子数组。

3结果

• 最终，ans 的值为 3。
• 函数返回 3，表示最短的满足条件的子数组长度是 3（即 [2, 3, 4]）。

很好这个滑动窗口是这样理解了，但是不会活学活用，那么下面继续

二.水果成篮

904. 水果成篮 - 力扣（LeetCode）

很抽象我读不懂题目：找了一个外援理解了一下题目

人话：我们的目标是找到一个窗口，其中只包含两种类型的水果，并且这个窗口尽可能大

步骤

1. 初始化: 定义两个变量来跟踪窗口的开始和结束位置。同时，使用一个数据结构（如哈希表）来跟踪窗口内不同水果的数量。

2. 扩大窗口: 从左向右移动窗口的右边界，即不断添加新的水果到窗口中，同时更新哈希表。

3. 满足条件的窗口: 当窗口中包含超过两种水果时，移动窗口的左边界以排除一种水果，直到窗口重新只包含两种水果。

4. 记录结果: 在每次更新窗口时，如果窗口只包含两种水果，更新最大收集水果的数量。

5. 重复直到结束: 继续扩大和缩小窗口，直到覆盖了整个数组。

例子

假设 fruits = [1, 2, 1, 2, 3]，我们可以按以下步骤使用滑动窗口法：

• 开始: 窗口为空，最大数量为 0。
• 窗口扩大: 添加 1，窗口为 [1]，最大数量为 1。
• 窗口扩大: 添加 2，窗口为 [1, 2]，最大数量为 2。
• 窗口扩大: 添加 1，窗口为 [1, 2, 1]，最大数量为 3。
• 窗口扩大: 添加 2，窗口为 [1, 2, 1, 2]，最大数量为 4。
• 窗口扩大: 添加 3，窗口为 [1, 2, 1, 2, 3]。现在窗口中有三种水果，需要缩小窗口。
• 缩小窗口: 移除窗口左边的 1，窗口变为 [2, 1, 2, 3]。依然有三种水果，继续缩小。
• 缩小窗口: 移除窗口左边的 2，窗口变为 [1, 2, 3]。现在窗口中有两种水果，最大数量更新为 3。

最终，最大收集的水果数量为 4（在添加第四个水果之前）。

初始设置

• basket = {}: 用来存储水果的类型和数量。
• start = 0: 窗口的开始位置。
• maxFruits = 0: 可以收集的最大水果数。
• fruits = [1, 2, 1, 2, 3]: 待处理的水果数组。

迭代过程

1. 第一次迭代 (end = 0):

   • fruit = fruits[0] = 1
   • basket = {1: 1}
   • maxFruits = Math.max(0, 0 - 0 + 1) = 1

2. 第二次迭代 (end = 1):

   • fruit = fruits[1] = 2
   • basket = {1: 1, 2: 1}
   • maxFruits = Math.max(1, 1 - 0 + 1) = 2

3. 第三次迭代 (end = 2):

   • fruit = fruits[2] = 1
   • basket = {1: 2, 2: 1}
   • maxFruits = Math.max(2, 2 - 0 + 1) = 3

4. 第四次迭代 (end = 3):

   • fruit = fruits[3] = 2
   • basket = {1: 2, 2: 2}
   • maxFruits = Math.max(3, 3 - 0 + 1) = 4

5. 第五次迭代 (end = 4):

   • fruit = fruits[4] = 3
   • basket = {1: 2, 2: 2, 3: 1}
   • 现在 basket 中有三种水果。需要移动 start 来删除一种水果。
   • 移动 start，basket = {1: 1, 2: 2, 3: 1}
   • 继续移动 start，basket = {2: 2, 3: 1}
   • maxFruits = Math.max(4, 4 - 1 + 1) = 4

结果

函数最终返回 maxFruits = 4。这意味着最长的符合规则的连续子数组是 [1, 2, 1, 2]，其长度为 4。