Completed
Dec 23, 2024
标签
数组
二分
双指针
滑动窗口
相关企业
难度
简单
- 题目描述：给定一个正整数数组和正整数target，计算数组中最小子数组的长度，满足子数组的和大于等于target
- 代码思路1：这道题有两个思路，滑动窗口和前缀和。滑动窗口即维护一个窗口，维护一个变量记录窗口内所有数字的和，如果这个和大于等于target则窗口左边缩小窗口直至小于target，每次缩小窗口都更新最短长度。如果不大于的话则向右扩大窗口。
- left表示左窗口，sum表示窗口内数字和，result表示最终要返回的最小子数组长度，right表示右窗口
- 右窗口不断向右扩张，sum不断更新，一旦遇到满足要求的sum时，贪心更新一下result，并尝试左窗口向右缩小，看看有没有更小的result，左窗口缩小时别忘了更新sum
- 最后判断result是否更新过，如果还是Integer.MAX_VALUE说明数组全部数字加起来都无法大于等于target
- 代码思路2：创建新数组记录原前缀和，因为题目说原始数组是正整数，因此前缀和数组一定是递增的，递增可以想到二分方法。首先以遍历新数组，使用二分法搜索满足要求的bound，不断更新bound-i的result
- 前缀和数组要比原数组多一位，第一位置0
- t为满足要求的最小的值，使用Java内置函数搜索返回bound
- 如果搜索到了，则bound可直接用，但如果没搜索到，对其取反或取负再减一，则得到右边稍大一点的数
- 最后判断如果bound在length范围内，则更新result
- 最后判断返回，同上
