LeetCode209.长度最小的子数组

9月8日 LeetCode209.长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

学习内容

题目的内容是给一个正整数的数组及目标值target，找到大于等于目标值的连续数组最小长度的区间。 容易想到的方法是两层for来遍历，分别表示区间终止位置和区间起始位置，然后把数组中所有区间的情况都遍历出来，找到大于等于s的最小区间长度。

用两个for来做起始位置和终止位置，两个指针中间的集合，更像是一个滑动窗口，滑动窗口可以用一个for来做两个for做的事。关键是理解清楚，用一个for来遍历，需要判断遍历的指针j是滑动窗口的起始还是终止位置。

1. 假设一个for遍历的j表示起始位置，那终止位置怎么遍历？

起始位置j指到哪里，终止位置都要把后面的元素都遍历一遍。才能返回所有以这个位置为起始位置的集合。再去判断集合中的所有元素，去收集大于等于s这些集合中的所有长度，从中取一个最小值。那结论就是：把一个for遍历的j当做是起始位置，终止位置依然要把所有位置遍历一遍，和暴力没区别。

2. 假设一个for遍历的j表示终止位置，那就需要一个动态移动的策略去移动起始位置。

滑动窗口解决的问题就是，如何一次性的找好移动的起始位置，for中的j已经确定了滑动窗口的终止位置。起始位置i就需要从开始一个个的往后移动，看是否满足集合和的条件，记录下符合条件的滑动窗口长度。每次移动到条件不满足时，就记录了终止位置j的最小区间长度。

代码

import (
    "fmt"
    "math"
)
func minSubArrayLen(target int, nums []int) int {
    i:=0
    result:=math.MaxInt64
    numssize:=len(nums)
    sum:=0
    for j:=0; j<numssize; j++{
        sum += nums[j]
        for sum>=target{
            subL:=j-i+1
            result=min(result,subL)
            sum=sum-nums[i]
            i++
        }
    }
    if result == math.MaxInt64{
        return 0
    }
    return result
}
func min(x ,y int) int{
    if x<y{
        return x
    } 
    return y
}

go补充

math.MaxInt64得到最大值

max和min函数的自定义实现

参考：

1. 获得Go中各种整数类型的最大值和最小值的方法 - 掘金:https://juejin.cn/post/7114479975251574792
2. go语言为什么没有min/max(int, int)函数:https://www.jianshu.com/p/4a833196b02c

标准代码的改进

优化点学习：

1. result不必设置为最大值，设置为长度值的最大即可，因此不需要用到math函数；
2. 不用写min函数，多次复用时再去写min。只用一次用一个if解决即可；

func minSubArrayLen(target int, nums []int) int {
  i:=0
  l:=len(nums)
  sum:=0
  // 这里不用设成最大值
  result:=l+1
  for j:=0;j<l;j++ {
    sum+=nums[j]
    for sum >= target{
      subLength:=j-i+1
      if subLength<result{
        result=subLength
      }
      sum-=nums[i]
      i++
    }
  }
  if result==l+1 {
    return 0
  }
  return result
}