算法刷题--长度最小的子数组
文章目录
1、209 长度最小的子数组
题目
代码：
intminSubArrayLen(int target,int* nums,int numsSize){int left =0,right =0;int sum =0;int min_len = INT_MAX;for(right =0;right < numsSize;right++){ sum += nums[right];while(sum >= target){ min_len =fmin(min_len,right-left+1); sum -= nums[left]; left++;}}return(min_len == INT_MAX)?0:min_len;}时间复杂度：O(n)
空间复杂度：O(1)
1. 观察切入点：为什么要用滑动窗口？
- 关键词：连续子数组。题目要求找到“连续”的段，这意味着我们不能破坏原数组的顺序（不能排序）。
- 关键词：正整数。这是一个极其重要的信号。因为数组里全是正整数，所以：
- 当你在一个区间里多加一个数，和（Sum）一定会变大。
- 当你在一个区间里少减一个数，和（Sum）一定会变小。
- 结论：这种“单调性”使得我们可以通过移动区间的左右边界来控制“和”的大小，而不需要暴力枚举所有可能的起点和终点（）。
2. 核心原理：滑动窗口（毛毛虫算法）
滑动窗口本质上是双指针的一种进阶应用。你可以把它想象成一条在数组上爬行的毛毛虫：
- **右边界
right**：负责寻找“可行解”。它不断向右伸展，把数字吃进来，直到窗口内的和满足≥ target。 - **左边界
left**：负责寻找“最优解”。一旦窗口满足条件，它就尝试向右收缩，看看在减掉左边的数字后，剩下的部分是否依然满足条件且长度更短。
3. 思路推演：逻辑如何一步步清晰？
我们要解决的核心矛盾是：如何在保证和不低于 target 的前提下，让区间尽可能短？
- 初始化：
left = 0,sum = 0,minLen = 无限大。 - 移动右边界：遍历数组，将
nums[right]加入sum。 - 判断与收缩（关键步骤）：
- **如果
sum >= target**： - 当前找到了一个满足条件的区间，计算长度
right - left + 1。 - 尝试更新
minLen。 - 最重要的一步：将
nums[left]从sum中减去，并将left右移。 - 重复执行：这是一个
while循环，因为可能减去一个数后，剩下的和依然>= target，我们要一直缩到不能再缩为止。
- 返回结果：如果
minLen没被动过，说明不存在满足条件的子数组，返回 0。
4. 避坑指南：这里的陷阱在哪里？
- 陷阱一：用
if代替while。
很多初学者在判断sum >= target时用了if。这会导致漏掉最优解。例如target=7, nums=[1, 1, 1, 1, 7]。当右指针指到7时，左指针可能需要连续右移很多次才能找到最小长度1。 - 陷阱二：初始化
minLen。
如果你把minLen初始化为0，那么比较currentLen < minLen永远不会成立。应该初始化为一个比数组长度还要大的数（如INT_MAX）。 - 陷阱三：复杂度理解。
虽然代码里有一个while嵌套在for循环里，但每个元素最多被right扫过一次，被left扫过一次。每个元素进出窗口各一次，所以时间复杂度是 O ( n ) O(n) O(n)，而不是 O ( n 2 ) O(n^2) O(n2)。
2、3 无重复字符的最长子串
题目：
代码：
intlengthOfLongestSubstring(char* s){int left =0,right =0;int cnt[128]={};//数组，也可以用哈希，因为说了s由英文字母、数字、符号和空格组成int count =0;for(right =0;s[right]!='\0';right++){int c = s[right]; cnt[c]++;while(cnt[c]>1){//窗口内有重复字符 cnt[s[left]]--;//移除窗口左端点字母 left++;//缩小窗口} count =fmax(count,right-left+1);//更新窗口长度最大值}return count;}时间复杂度：O(n)
空间复杂度：O(1)或者O(128)
3、 713 乘积小于K的子数组
题目：
代码：
intnumSubarrayProductLessThanK(int* nums,int numsSize,int k){if(k <=1)return0;int left =0,right =0;int count =0;int prod=1;for(right =0;right < numsSize;right++){ prod *= nums[right];while(prod >= k){ prod /= nums[left]; left++;} count +=(right - left +1);}return count;}时间复杂度：O(n)
空间复杂度：O(1)
为什么这里prod初始化为1而加法中count一般初始化为0？
这是一个关于代数恒等元（Identity Element）和逻辑初始化的经典问题。
1. 核心原理：乘法与加法的“起点”不同
在数学中，每一个运算都有一个“不改变结果”的初始值：
- 加法的恒等元是 0：任何数加上 0，结果不变（）。
- 乘法的恒等元是 1：任何数乘以 1，结果不变（）。
在你的代码中：
你正在计算乘积（prod）。
- 如果初始化为
prod = 0：那么无论你后面乘以什么数（0 * nums[right]），结果永远都是 0。这会导致你的循环逻辑完全失效。 - 如果初始化为
prod = 1：当你乘以第一个数nums[0]时，1 * nums[0]得到了数组的第一个数，这才是正确的累乘起点。
2. 观察切入点：这行代码的“计数逻辑”
这道题最精妙的地方在于 count += (right - left + 1);。我们要思考：为什么是加这个长度？
- 推演过程：
假设当前的有效窗口是[left, right]，比如[2, 5, 6]。
当我们把right指向的新元素包含进来时，新增加的满足条件的连续子数组有：
[6](只有新元素自己)[5, 6](新元素和它前一个)[2, 5, 6](新元素和它前两个)
正好是 3 个，也就是right - left + 1的长度。
3. 思路深度拆解：为什么要有 if(k <= 1) return 0;？
这也是你代码中非常鲁棒（Robust）的一点。
- 切入点：题目要求乘积严格小于
k。 - 逻辑推导：
- 如果
k = 1：因为数组里全是正整数（），任何子数组的乘积至少是 1。不可能有乘积比 1 还小的子数组。 - 如果
k = 0：同理，正整数乘积不可能小于 0。 - 结论：如果没有这个判断，当
k=1时，while(prod >= k)会陷入死循环（因为1 >= 1永远成立，left会一直加到越界）。这行代码不仅是优化，更是防线。
4. 避坑指南：数据溢出
虽然这道题你写对了，但在实际应用中要小心：
- 风险：
prod是一直累乘的。如果数组里有很多大数，prod可能会超过int能表示的最大范围（约 ）。 - 对策：在某些题目中，可能需要将
prod定义为long long。
总结
- 乘法初始化用 1，加法初始化用 0。
- 滑动窗口计数：
right - left + 1是统计“以right结尾的所有合法子数组数量”的常用公式。
你现在已经掌握了滑动窗口的：
- 求最小长度（209题）
- 求最大长度（3题）
- 求子数组个数（713题）
这三种模式涵盖了滑动窗口 80% 的考点！
4 904 水果成蓝
题目
滑动窗口的套路其实就是：
“右指针无脑进，左指针按需缩，中间过程存结果”
代码
inttotalFruit(int* fruits,int fruitsSize){int left =0,right =0;int count =0;int n = fruitsSize;//int cnt[n+1] = {};int* cnt =(int*)calloc(sizeof(int),(fruitsSize+1));if(cnt ==NULL)return0;//增加鲁棒性int kinds =0;for(right =0;right < n;right++){int a = fruits[right];if(cnt[a]==0){ kinds++;} cnt[a]++;while(kinds >2){ cnt[fruits[left]]--;if(cnt[fruits[left]]==0){ kinds--;} left++;} count =fmax(right - left +1,count);}return count;}时间复杂度：O(n)
空间复杂度：O(n)或者O(fruitsSize+1)
使用哈希表版
//1.定义哈希表结构structHashTable{int id;//键（水果种类）int count;//值（该种类在窗口内的数量） UT_hash_handle hh;//必选句柄};inttotalFruit(int* fruits,int fruitsSize){structHashTable* map =NULL;//初始化哈希表头int left =0,right =0,maxLen =0,kinds =0;for(right =0;right < fruitsSize;right++){int r_fruit = fruits[right];structHashTable* item;//---窗口右扩：添加哈希项---HASH_FIND_INT(map,&r_fruit,item);if(item ==NULL){ item =(structHashTable*)malloc(sizeof(structHashTable)); item->id = r_fruit; item->count =1;HASH_ADD_INT(map,id,item); kinds++;//发现新种类}else{ item->count++;}//---窗口左缩：种类超过2 时执行---while(kinds >2){int l_fruit = fruits[left];structHashTable* del_item;HASH_FIND_INT(map,&l_fruit,del_item);if(del_item){ del_item->count--;if(del_item->count ==0){//核心：计数归零必须从表里删除，kinds才会变HASH_DEL(map,del_item);free(del_item); kinds--;}} left++;}//更新结果int currentLen = right - left +1;if(currentLen > maxLen){ maxLen = currentLen;}}//---善后：释放哈希表内存structHashTable*curr,*tmp;HASH_ITER(hh,map,curr,tmp){HASH_DEL(map,curr);free(curr);}return maxLen;}不懂哈希表的友友可以看看下面gimini老师的解释：
在 C 语言中，uthash 是一个非常流行的宏库，它允许你像使用高级语言（如 Python 的字典或 Java 的 HashMap）一样处理数据。
由于 C 语言本身没有内置哈希表，这段代码利用了 uthash 的宏（如 HASH_FIND_INT）来实现**“快速查找”**。
1. 观察切入点：为什么要用哈希表？
在这道题里，我们要记录窗口内每种水果出现的次数。
- 数组法：只能处理水果编号是连续小整数的情况。
- 哈希表法：水果编号可以是任何数字（比如
1和999999）。哈希表通过一个“哈希函数”，把这些杂乱的编号映射到表里的位置，让你能在 时间内找到这个水果采了多少个。
2. 核心原理：结构体与“句柄”
structHashTable{int id;// 键 (Key)：水果的编号（唯一的）int count;// 值 (Value)：这个水果在当前窗口里有多少个 UT_hash_handle hh;// 句柄：这是 uthash 的内部结构，不用管它，但必须写};把哈希表想象成一个记事本，每一页（struct）记录了一种水果的信息。hh 就像是装订线，把所有页面连在一起。
3. 推演过程：代码逐段解析
A. 查找与入队（右窗口扩张）
HASH_FIND_INT(map,&r_fruit, item);// 1. 在记事本 map 里找编号为 r_fruit 的页if(item ==NULL){// 2. 没找到，说明是新种类 item =malloc(...);// 3. 拿一张新纸 item->id = r_fruit;// 4. 写上水果编号 item->count =1;// 5. 初始数量为 1HASH_ADD_INT(map, id, item);// 6. 把这张纸装订进记事本 kinds++;// 7. 种类加 1}else{ item->count++;// 8. 找到了，直接在数量上 +1}B. 满足条件的极限（左窗口收缩）
当 kinds > 2 时，我们需要丢掉最左边的水果（left 指针移动）。
del_item->count--;// 1. 数量减 1if(del_item->count ==0){// 2. 如果减到 0，说明这种水果在窗口里消失了HASH_DEL(map, del_item);// 3. 从记事本里撕掉这一页free(del_item);// 4. 毁掉这张纸（释放内存） kinds--;// 5. 种类减 1}注意：在哈希表中，count == 0的项必须删除。如果不撕掉这一页，即使数量是 0，程序依然会认为这种水果“存在”，kinds就不会减少。
C. 善后处理（内存回收）
C 语言不会自动回收 malloc 的空间。
HASH_ITER(hh, map, curr, tmp){// 遍历记事本的每一页HASH_DEL(map, curr);// 撕掉free(curr);// 销毁}如果你在力扣上不写这段，可能会报“内存泄漏”警告，虽然通常能过，但在实际开发中这是导致程序崩溃的头号元凶。
4. 避坑指南：哈希表的“暗号”
使用 uthash 有几个必须遵守的暗号：
- 初始化必为 NULL：
struct HashTable* map = NULL;必须赋值为NULL，否则宏会报错。 - 查找要传地址：
HASH_FIND_INT的第二个参数必须是地址&r_fruit。 - Key 必须唯一：哈希表里不能有两页的
id是一样的。
5. 总结：滑动窗口 + 哈希表的万能公式
这道题的逻辑其实可以套用到很多题：
- 进：
right进场，哈希表记录（count++），如果是新 Key 则kinds++。 - 出：当
kinds不满足条件，left出场，哈希表更新（count--），如果count == 0则彻底删除并kinds--。 - 算：每次记录窗口大小
right - left + 1。
你理解了为什么要特意执行 HASH_DEL 吗？ 它是为了让 kinds 能正确地反映“当前窗口内真实存在的水果种类”。
5、76 最小覆盖子串
题目
代码
hard还是太难了~
bool is_covered(int cnt_s[],intcnt_t[]){for(int i ='A';i <='Z';i++){if(cnt_s[i]<cnt_t[i]){return false;}}for(int i ='a';i <='z';i++){if(cnt_s[i]<cnt_t[i]){return false;}}return true;}char*minWindow(char* s,char* t){int cnt_s[128]={};//s子串字母的出现次数intcnt_t[128]={};//t子串字母的出现次数for(int i =0;t[i];i++){cnt_t[t[i]]++;}int ans_left =-1,ans_right = INT_MAX /2;int left =0;for(int right =0;s[right];right++){//移动子串右端点 cnt_s[s[right]]++;//右端点字母移入子串while(is_covered(cnt_s,cnt_t)){//涵盖if(right - left < ans_right - ans_left){//找到更短的子串 ans_left = left;//记录此时的左右端点 ans_right = right;} cnt_s[s[left]]--;//左端点字母移出子串 left++;}}if(ans_left <0){return"";} s[ans_right +1]='\0';return s + ans_left;}时间复杂度：O(n)
空间复杂度：O(128)
灵神优化版
char*minWindow(char* s,char* t){int cnt[128]={};int less =0;for(int i =0;t[i];i++){if(cnt[t[i]]==0){ less++;} cnt[t[i]]++;}int ans_left =-1;int left =0;int ans_right = INT_MAX /2;for(int right =0;s[right];right++){int c = s[right]; cnt[c]--;if(cnt[c]==0){ less--;}while(less ==0){if((right - left)<(ans_right - ans_left)){ ans_left = left; ans_right = right;}if(cnt[s[left]]==0){ less++;} cnt[s[left]]++; left++;}}if(ans_left <0){return"";} s[ans_right +1]='\0';return s + ans_left;}力扣第 76 题 “最小覆盖子串” (Minimum Window Substring) 是滑动窗口题目中的“天花板”。它几乎融合了我们之前学过的所有技巧：双指针、哈希表计数、以及窗口的动态伸缩。
这道题的难度在于条件的复杂性：你不仅要找包含 t 中所有字符的窗口，还要处理重复字符，并保证它是最短的。
1. 观察切入点：为什么要用滑动窗口？
- 目标：寻找一段连续的区间（子串），使其满足某种特定条件（包含
t的所有字符）。 - 单调性：当你增加窗口右边界时，满足条件的可能性在增加；当你收缩左边界时，如果依然满足条件，窗口就变短了。
- 暴力代价：如果枚举所有子串，复杂度是 。使用滑动窗口可以将复杂度降为 。
2. 核心原理：两个哈希表的对比
我们需要两个“记事本”（哈希表）：
need表：记录字符串t中每个字符出现的次数（目标）。window表：记录当前滑动窗口中每个字符出现的次数（现状）。
**关键变量 valid**：
为了不每次都遍历整个哈希表来检查是否“覆盖”，我们定义 valid 变量来记录：窗口内有多少个字符已经达到了 need 表中的要求数量。
3. 思路推演：逻辑四部曲
第一步：右移 right（扩张）
不断增加 right 指针扩大窗口。每进一个字符：
- 如果它是
t中的字符，更新window表。 - 如果
window中该字符的数量刚好等于need中的要求，valid++。
第二步：判断收缩（找到可行解）
当 valid == need中的字符种类数 时，说明窗口已经包含了 t 的所有字符。
第三步：左移 left（优化）
此时我们要找“最小”子串，所以尝试把 left 往右挪。
- 每挪动一次，更新
minLen。 - 每挪动一次，都要把
left处的字符从window中踢出。 - 如果踢出后，该字符的数量小于
need中的要求，则valid--。此时窗口不再满足条件，停止收缩。
第四步：重复上述步骤
直到 right 到达字符串末尾。
4. 代码实现（C语言+数组哈希版）
在 C 语言中，处理 ASCII 字符，直接用 int[128] 数组模拟哈希表效率最高。
char*minWindow(char* s,char* t){int need[128]={0}, window[128]={0};int t_len =0;// 统计 t 中字符频率for(int i =0; t[i]; i++){if(need[t[i]]==0) t_len++;// 统计有多少种不同的字符 need[t[i]]++;}int left =0, right =0;int valid =0;// 已达标的字符种类数int start =0, minLen = INT_MAX;// 记录最小窗口的起始位置和长度while(s[right]){char c = s[right]; right++;// 窗口右移// 更新窗口数据if(need[c]>0){ window[c]++;if(window[c]== need[c]) valid++;}// 判断窗口是否收缩while(valid == t_len){// 更新最小覆盖子串if(right - left < minLen){ start = left; minLen = right - left;}char d = s[left]; left++;// 窗口左移// 更新窗口数据if(need[d]>0){if(window[d]== need[d]) valid--; window[d]--;}}}if(minLen == INT_MAX)return"";// 返回截取的子串char* result =(char*)malloc(sizeof(char)*(minLen +1));strncpy(result, s + start, minLen); result[minLen]='\0';return result;}5. 避坑指南
valid的更新逻辑：一定要是window[c] == need[c]时才valid++。如果写成window[c] >= need[c]，会导致valid多次增加。start指针的作用：不要在循环里反复malloc或strncpy。只记录start和minLen，最后统一生成结果字符串。- 空字符串处理：注意
minLen是否被更新过的逻辑判断。
总结：滑动窗口的终极模板
通过这道题，你可以总结出一个万能模板：
- 右指针进场，更新窗口数据。
- 收缩条件触发（本题是
valid == t_len，209 题是sum >= target）。 - 左指针进场，尝试缩小窗口并寻找最优解。
- 循环往复。
至此，你已经完成了滑动窗口专题的全部“通关”！
杂记
在第五题中int ans_left = -1;为什么要令这个等于-1？
在算法编程中，将 ans_left 初始化为 -1 是一个非常经典且严谨的**“标记位”**设计。它的作用主要体现在以下两个方面：
1. 观察切入点：作为“从未找到”的信号灯
滑动窗口的目标是寻找满足条件的子串。但在实际运行中，可能会出现整个字符串 s 都不包含 t 的所有字符的情况。
- **初始化为
-1**：这是一个无效的数组索引。 - 逻辑判断：在代码最后，我们检查
if (ans_left < 0)。 - 如果
ans_left依然是-1，说明整个循环跑完都没有一次进过while里的if判断（即没找到可行解）。 - 这时我们直接返回空字符串
""。
如果没有这个初始化：
如果你令 ans_left = 0，而在寻找过程中一次都没找到满足条件的子串，代码最后可能会错误地返回从索引 0 开始的一段字符串，导致结果错误。
2. 逻辑推演：为了第一次“成功记录”
在你的更新逻辑中：
if((right - left)<(ans_right - ans_left)){ ans_right = right; ans_left = left;}- 第一次找到可行解时：
由于ans_right初始化为一个极大的值（INT_MAX/2），而ans_left是-1，这个减法结果ans_right - (-1)会是一个巨大的正数。 - 结果：这保证了只要找到第一个满足条件的子串，
if条件一定成立，从而把第一个真实有效的left和right存入这两个变量中，覆盖掉初始的-1。
3. 思路总结：状态机思维
在 C 语言处理这类搜索问题时，通常遵循这个套路：
- 初始态：设置一个不可能的标志（如
-1或NULL）。 - 寻找态：如果找到，更新标志为真实值。
- 结果态：通过判断标志是否被修改过，来决定是返回结果还是返回“未找到”。
4. 避坑指南：为什么不用 0？
在数组操作中，0 是一个合法索引（代表第一个元素）。
如果你用 0 作为初始值，你就分不清：
- “结果是真的从索引
0开始” - “还是根本就没找到结果，只是沿用了初始值”
这就是为什么程序员喜欢用 -1 来代表**“不存在”**。
至此，滑动窗口所有的“潜规则”你都掌握了！ 这种对初始值的敏感度是成为高级程序员的必备素质。
