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

《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;
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30

• 前缀和 + 二分查找——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;
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63

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;
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44

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);
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59

• 滑动窗口——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);
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66

---