《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);} }