[LeetCode][Golang] 209. 长度最小的子数组

智数映星客
• 阅读 862

题目:

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

题解一:

滑动窗口可以很好的解决。先贴代码(Go):

func minSubArrayLen(target int, nums []int) int {
   l, r, n, minValue := 0, 0, len(nums), math.MaxInt32 //[i,r]
   sum := 0
   for r < n && l <= r {
      sum += nums[r]
      for sum >= target {
         minValue = min(minValue, r-l+1)
         sum -= nums[l]
         l++
      }
      r++
   }

   if minValue == math.MaxInt32 {
      return 0
   }
   return minValue
}

func min(a int, b int) int {
   if a < b {
      return a
   }
   return b
}

核心思想是:

  • 右移 r 时,子数组和变大,因此和不够时,右移 r
  • 右移 l 时,子数组长度变小,因此和足够时,左移 l
  • 当右移 r 使得子数组和满足条件时,立刻寻找符合条件的最右的 l 并记录。
  • 当右移 l 使得子数组和不满足条件时,立刻寻找符合条件的最左的 r 并记录。

在不满足时优先满足条件,在满足条件时优先降低消耗(子数组长度),可谓是 贪心算法

比暴力求解少遍历很多情况,例如:(n 为合适的正整数)

  • 当我们知道 [l,r] 满足条件时,[l,r+n] 范围内的子数组不再考虑,因为它一定也满足条件但是比 [l,r] 更长。
  • 当我们知道 [l,r] 不满足条件时,[l+n,r] 范围内的子数组不再考虑。因为它一定也不满足条件。

复杂度分析:

时间复杂度:O(n),其中 n 是数组的长度。指针 lr 最多各移动 n 次。
空间复杂度:O(1)

题解二:

题目在进阶中,有个奇怪的要求:如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

好!很有精神!

其实就是为了锻炼下 前缀和 的方法,先贴代码(Go):

func minSubArrayLen(s int, nums []int) int {
   n := len(nums)
   if n == 0 {
      return 0
   }
   ans := math.MaxInt32
   sums := make([]int, n+1)
   // 为了方便计算,令 size = n + 1
   // sums[0] = 0 意味着前 0 个元素的前缀和为 0
   // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
   // 以此类推
   for i := 1; i <= n; i++ {
      sums[i] = sums[i-1] + nums[i-1]
   }
   for i := 0; i <= n; i++ {
      target := s + sums[i]
      bound := sort.SearchInts(sums, target)
      if bound <= n {
         ans = min(ans, bound-(i))
      }
   }
   if ans == math.MaxInt32 {
      return 0
   }
   return ans
}
func min(a int, b int) int {
   if a < b {
      return a
   }
   return b
}

每个 sums 元素使用一次 二分搜索 ,成功将复杂度升到了 O(nlogn)

至于 前缀和 的方法,Emmmmmmmm,以后再说,题目的奇怪要求,在这里使用,不合我意。

复杂度分析:

时间复杂度:O(nlogn),其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标,遍历的时间复杂度是 O(n),对于每个开始下标,需要通过二分查找得到长度最小的子数组,二分查找得时间复杂度是 O(logn),因此总时间复杂度是 O(nlogn)

空间复杂度:O(n),其中 n 是数组的长度。额外创建数组 sums 存储前缀和。

点赞
收藏
评论区
推荐文章
blmius blmius
4年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
7个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
胡哥有话说 胡哥有话说
4年前
面试官在“逗”你系列:连续子数组的最大和或最小和
前言本文题目是“连续子数组的最大和或最小和”。话不多说,开始“打怪”修炼...一、理解题目以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组的和,找寻最大值。如在数组3,2,1,2,4,6,5中连续子数组的最大和为:3(2)1248输入:3,2,1,2,4,6,
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
Stella981 Stella981
3年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Stella981 Stella981
3年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Stella981 Stella981
3年前
JavaScript常用函数
1\.字符串长度截取functioncutstr(str,len){vartemp,icount0,patrn/^\x00\xff/,strre"";for(vari
Wesley13 Wesley13
3年前
ES6 新增的数组的方法
给定一个数组letlist\//wu:武力zhi:智力{id:1,name:'张飞',wu:97,zhi:10},{id:2,name:'诸葛亮',wu:55,zhi:99},{id:3,name:'赵云',wu:97,zhi:66},{id:4,na
达里尔 达里尔
1年前
给数组添加新数据,判断数据是否重复
多选要进行数组拼接,希望判断往原数组里添的新数据是否重复,封装个简易方法languageconstdataArrayname:'aaa',id:1,name:'bbb',id:2;constnewDataname:'ccc',id:2;//要添加的新数
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这