郑州网站推建设,国外可以做网站盈利模式有哪些,晨光科技 网站建设,品牌建设的最高境界是培育客户的2023.6.1 这道题的关键是滑动窗口法#xff0c;滑动窗口法应设定好窗口左侧的右移条件与窗口右侧的移动条件 本例中先初始化好用到的各种值 循环的终止条件是滑动窗口右侧超出列表的范围 走来 cur_sum nums[right] 是将cur_sum的值更新为当前滑动窗口[left,right]的值之和 接…2023.6.1 这道题的关键是滑动窗口法滑动窗口法应设定好窗口左侧的右移条件与窗口右侧的移动条件 本例中先初始化好用到的各种值 循环的终止条件是滑动窗口右侧超出列表的范围 走来 cur_sum nums[right] 是将cur_sum的值更新为当前滑动窗口[left,right]的值之和 接着通过内循环判断滑动窗口左侧要向右走多少这是因为如果num[right]值很大此时右侧添加进来一个值需要左侧吐出去好几个值才能重新将cur_sum缩小到target 内循环中左侧每吐出一个一个left 1 内循环结束时[left,right]的值之和恰好小于target 此时right1开始下次外循环
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) - int:l len(nums)left 0right 0min_len float(inf)cur_sum 0 #当前的累加值while right l:cur_sum nums[right]while cur_sum s: # 当前累加值大于目标值min_len min(min_len, right - left 1)cur_sum - nums[left]left 1right 1return min_len if min_len ! float(inf) else 0为什么滑动窗口法的时间复杂度是n虽然是双循环结构但实际上每个元素被纳入滑动窗口和吐出滑动窗口时各执行了一次相当于每个元素一定被执行2次因此O(2n) ⇒ O(n)
暴力解法 就是通过双循环得到所有可能的子列表然后判断每个子列表是否符合条件最后找到最短的子列表 这玩意执行直接超出时间限制
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:l len(nums)min_ l 1for i in range(l):for j in range(i,l):temp nums[i:j1]if sum(temp) target:min_ min(min_, len(temp))return min_ if min_ ! l 1 else 0总共循环1 2 3 … n (n^2 n)/2因此时间复杂度为O(n^2)
