《LeetCode力扣练习》代码随想录——数组（长度最小的子数组

数组（长度最小的子数组"/>

《LeetCode力扣练习》代码随想录——数组（长度最小的子数组

《LeetCode力扣练习》代码随想录——数组（长度最小的子数组—Java）

刷题思路来源于 代码随想录

209. 长度最小的子数组

• 滑动窗口——O(n)

  class Solution {public int minSubArrayLen(int target, int[] nums) {if(nums.length==1){return nums[0]>=target?1:0;}int slow=0;int fast=0;int sum=0;int result=Integer.MAX_VALUE;for(;fast<nums.length;fast++){sum+=nums[fast];while(sum>=target){int temp=fast-slow+1;result=temp<result?temp:result;sum-=nums[slow++];}}return result==Integer.MAX_VALUE?0:result;}
  }
  

• 前缀和 + 二分查找——O(n log(n))

  class Solution {public int minSubArrayLen(int target, int[] nums) {if(nums.length==0){return 0;}int[] sum=new int[nums.length+1];int result=Integer.MAX_VALUE;for(int i=1;i<nums.length+1;i++){sum[i]=sum[i-1]+nums[i-1];}for(int i=1;i<nums.length+1;i++){int newTarget=target+sum[i-1];int location=binarySearch(newTarget,sum);if(location<0){location=-(location+1);}int temp=location-(i-1);if(location<=nums.length){result=result<temp?result:temp;}}return result==Integer.MAX_VALUE?0:result;}public int binarySearch(int target, int[] nums){if(nums.length==0){return -1;}int left=0;int right=nums.length-1;while(left<=right){int middle=(left+right)>>>1;if(nums[middle]>target){right=middle-1;}else if(nums[middle]<target){left=middle+1;}else{return middle;}}return -left-1;}
  }
  

904. 水果成篮

• 滑动窗口——O(n)

  class Solution {public int totalFruit(int[] fruits) {if(fruits.length==1){return 1;}int slow=0;int fast=0;int[] map=new int[fruits.length];int size=0;int result=Integer.MIN_VALUE;for(;fast<fruits.length;fast++){if(map[fruits[fast]]==0){size++;}map[fruits[fast]]++;while(size>2){map[fruits[slow]]--;if(map[fruits[slow]]==0){size--;}slow++;}int temp=fast-slow+1;result=result<temp?temp:result;}return result==Integer.MIN_VALUE?0:result;}
  }
  

76. 最小覆盖子串

• 滑动窗口——O(n+m)

  正常的常规写法

  class Solution {public String minWindow(String s, String t) {if(s.length()==1&&t.length()==1){return s.equals(t)?s:"";}int size=0;int[] charS=new int[60];int[] charT=new int[60];for(int i=0;i<t.length();i++){if(charT[getLocation(t.charAt(i))]++==0){size++;}}int slow=0;int fast=0;String result=s+'#';for(;fast<s.length();fast++){int locationFast=getLocation(s.charAt(fast));if(charT[locationFast]>0&++charS[locationFast]==charT[locationFast]){size--;}while(size==0){String temp=s.substring(slow,fast+1);result=temp.length()<result.length()?temp:result;int locationSlow=getLocation(s.charAt(slow));if(charT[locationSlow]>0&charS[locationSlow]--==charT[locationSlow]){size++;}slow++;}}return result.length()==s.length()+1?"":result;}public int getLocation(char ch){return ('A'<=ch&&ch<='Z')?(ch-'A'):(ch-'a'+26);}
  }
  

• 滑动窗口——O(n+m)

  由于 substring 函数操作字符串比较费时，导致同样是滑动窗口，将更新结果值的操作拿到 while 循环外面可以大幅度地优化时间

  class Solution {public String minWindow(String s, String t) {if(s.length()==1&&t.length()==1){return s.equals(t)?s:"";}int size=0;int[] charS=new int[60];int[] charT=new int[60];for(int i=0;i<t.length();i++){if(charT[getLocation(t.charAt(i))]++==0){size++;}}int slow=0;int fast=0;String result=s+'#';for(;fast<s.length();fast++){int locationFast=getLocation(s.charAt(fast));if(charT[locationFast]>0&++charS[locationFast]==charT[locationFast]){size--;}int a=-1;int b=-1;while(size==0){a=slow;b=fast;int locationSlow=getLocation(s.charAt(slow));if(charT[locationSlow]>0&charS[locationSlow]--==charT[locationSlow]){size++;}slow++;}if(a!=-1&&b!=-1){String temp=s.substring(a,b+1);result=temp.length()<result.length()?temp:result;}}return result.length()==s.length()+1?"":result;}public int getLocation(char ch){return ('A'<=ch&&ch<='Z')?(ch-'A'):(ch-'a'+26);}
  }