做网站建设销售,互联网行业前景分析,西安知名网站推广,服务器分配网络提高网站访问速度【力扣】 209. 长度最小的子数组 文章目录 【力扣】 209. 长度最小的子数组1. 题目介绍2. 解法2.1 暴力求解2.2 前缀和 二分查找2.3 滑动窗口2.4 贪心回溯 3. Danger参考 1. 题目介绍
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 …【力扣】 209. 长度最小的子数组 文章目录 【力扣】 209. 长度最小的子数组1. 题目介绍2. 解法2.1 暴力求解2.2 前缀和 二分查找2.3 滑动窗口2.4 贪心回溯 3. Danger参考 1. 题目介绍
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 2. 解法
2.1 暴力求解
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) - int:if not nums:return 0n len(nums)ans n 1for i in range(n):total 0for j in range(i, n):total nums[j]if total s:ans min(ans, j - i 1)breakreturn 0 if ans n 1 else ans2.2 前缀和 二分查找
方法一的时间复杂度是 O(n2)因为在确定每个子数组的开始下标后找到长度最小的子数组需要 O(n) 的时间。如果使用二分查找则可以将时间优化到 O(logn)总的变为O(nlogn) -因为这道题保证了数组中每个元素都为正所以前缀和一定是递增的这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正这里就不能使用二分来查找这个位置了。
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) - int:if not nums:return 0n len(nums)ans n 1sums [0]for i in range(n):sums.append(sums[-1] nums[i])for i in range(1, n 1):target s sums[i - 1]bound bisect.bisect_left(sums, target)if bound ! len(sums):ans min(ans, bound - (i - 1))return 0 if ans n 1 else ans2.3 滑动窗口
在方法一和方法二中都是每次确定子数组的开始下标然后得到长度最小的子数组因此时间复杂度较高。为了降低时间复杂度可以使用滑动窗口的方法。
定义两个指针 start 、end 分别表示子数组滑动窗口窗口的开始位置和结束位置维护变量 sum 存储子数组中的元素和即从 start - end 的元素和。
初始状态下start 和 end 都指向下标 0sum 的值为 0。
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) - int:if not nums:return 0n len(nums)ans n 1start, end 0, 0total 0while end n:total nums[end]while total s:ans min(ans, end - start 1)total - nums[start]start 1end 1return 0 if ans n 1 else ans2.4 贪心回溯
class Solution:def hs(self, nums, sum, left, right, target):if sum target:return 0;if leftright:if nums[left]nums[right]:sum - nums[right]if sum target:return self.hs(nums, sum, left, right-1, target)elif nums[left]nums[right]:sum - nums[left]if sum target:return self.hs(nums, sum, left1, right, target)else:tmp sum - nums[left]if tmp target:a self.hs(nums, tmp, left1, right, target)b self.hs(nums, tmp, left, right-1, target)return min(a,b)return right-left1def minSubArrayLen(self, target: int, nums: List[int]) - int:n len(nums)sum 0for i in range(n):sum nums[i]ans self.hs(nums, sum, 0, n-1, target)return ans3. Danger
力扣LeetCode是领扣网络旗下专注于程序员技术成长和企业技术人才服务的品牌。源自美国硅谷力扣为全球程序员提供了专业的IT技术职业化提升平台有效帮助程序员实现快速进步和长期成长。此外力扣LeetCode致力于解决程序员技术评估、培训、职业匹配的痛点逐步引领互联网技术求职和招聘迈向专业化。
据了解到的情况Easy题和Medium 题在面试中比较常见通常会以手写代码之类的形式出现您需要对问题进行分析并给出解答并于面试官进行交流沟通有时还会被要求分析时间复杂度8与空间复杂度°面试官会通过您对题目的分析解答了解您对常用算法的熟悉程度和您的程序实现功底。而在一些对算法和程序实现功底要求较高的岗位Hard 题也是很受到面试官的青睐如果您在面试中成功Bug-Free出一道Hard题我们相信您一定会给面试官留下很深刻的印象并极大增加拿到Offer的概率据相关人士统计如果您在面试成功解出一道Hard题拿不到Offer的概率无限接近于0。所以,力扣中Easy和Medium相当于面试中的常规题而Hard 则相当于面试中较难的题解出—道Hard题Offer可以说是囊中之物。
参考
【1】https://leetcode.cn/problems/minimum-size-subarray-sum/description/
