【問題描述】[中等]
給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組，并返回其長度。如果不存在符合條件的連續子數組，返回 0。示例: 輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數組 [4,3] 是該條件下的長度最小的連續子數組。
【解答思路】
1. 暴力法
- 初始化子數組的最小長度為無窮大
- 枚舉數組nums 中的每個下標作為子數組的開始下標，對于每個開始下標 i，需要找到大于或等于 i 的最小下標 j，使得從 nums[i] 到nums[j] 的元素和大于或等于 s，并更新子數組的最小長度（此時子數組的長度是 j-i+1）。
時間復雜度：O(N^2) 空間復雜度：O(1)
class Solution {public int minSubArrayLen(int s
, int[] nums
) {int n
= nums
.length
;if (n
== 0) {return 0;}int ans
= Integer
.MAX_VALUE
;for (int i
= 0; i
< n
; i
++) {int sum
= 0;for (int j
= i
; j
< n
; j
++) {sum
+= nums
[j
];if (sum
>= s
) {ans
= Math
.min(ans
, j
- i
+ 1);break;}}}return ans
== Integer
.MAX_VALUE
? 0 : ans
;}
}
2. 前綴和
時間復雜度：O(N^2) 空間復雜度：O(N)
public int minSubArrayLen(int s
, int[] nums
) {int n
= nums
.length
;if (n
== 0) {return 0;}int[] sums
= new int[n
];sums
[0] = nums
[0];for (int i
= 1; i
< n
; i
++) {sums
[i
] = nums
[i
] + sums
[i
- 1];}int min
= Integer
.MAX_VALUE
;for (int i
= 0; i
< n
; i
++) {int s2
= s
- nums
[i
]; for (int j
= i
; j
< n
; j
++) {if (sums
[j
] - sums
[i
] >= s2
) {min
= Math
.min(min
, j
- i
+ 1);}}}return min
== Integer
.MAX_VALUE
? 0 : min
;
}
3. 前綴和+二分
時間復雜度：O(NlogN) 空間復雜度：O(N)
class Solution {public int minSubArrayLen(int s
, int[] nums
) {int n
= nums
.length
;if (n
== 0) {return 0;}int ans
= Integer
.MAX_VALUE
;int[] sums
= new int[n
+ 1]; for (int i
= 1; i
<= n
; i
++) {sums
[i
] = sums
[i
- 1] + nums
[i
- 1];}for (int i
= 1; i
<= n
; i
++) {int target
= s
+ sums
[i
- 1];int bound
= Arrays
.binarySearch(sums
, target
);if (bound
< 0) {bound
= -bound
- 1;}if (bound
<= n
) {ans
= Math
.min(ans
, bound
- (i
- 1));}}return ans
== Integer
.MAX_VALUE
? 0 : ans
;}
}
另一寫法
public int minSubArrayLen(int s
, int[] nums
) {int n
= nums
.length
;if (n
== 0) {return 0;}int[] sums
= new int[n
];sums
[0] = nums
[0];for (int i
= 1; i
< n
; i
++) {sums
[i
] = nums
[i
] + sums
[i
- 1];}int min
= Integer
.MAX_VALUE
;for (int i
= 0; i
< n
; i
++) {int s2
= s
- nums
[i
];int k
= binarySearch(i
, n
- 1, sums
, s2
+ sums
[i
]);if (k
!= -1) {min
= Math
.min(min
, k
- i
+ 1);}}return min
== Integer
.MAX_VALUE
? 0 : min
;
}
private int binarySearch(int start
, int end
, int[] sums
, int target
) {int mid
= -1;while (start
<= end
) {mid
= (start
+ end
) >>> 1;if (sums
[mid
] == target
) {return mid
;} else if (sums
[mid
] < target
) {start
= mid
+ 1;} else {end
= mid
- 1;}}return sums
[mid
] > target
? mid
: -1;
}
4. 雙指針
時間復雜度：O(N) 空間復雜度：O(1)
class Solution {public int minSubArrayLen(int s
, int[] nums
) {int n
= nums
.length
;if (n
== 0) {return 0;}int ans
= Integer
.MAX_VALUE
;int start
= 0, end
= 0;int sum
= 0;while (end
< n
) {sum
+= nums
[end
];while (sum
>= s
) {ans
= Math
.min(ans
, end
- start
+ 1);sum
-= nums
[start
];start
++;}end
++;}return ans
== Integer
.MAX_VALUE
? 0 : ans
;}
}
【總結】
1.涉及連續子數組的問題，我們通常有兩種思路：一是滑動窗口、二是前綴和
2.二分查找的關鍵就是那個遞增的有序數列，從而可以每次拋棄一半的可選解。
3.Arrays類的binarySearch()方法
轉載鏈接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
參考鏈接https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-43/
參考鏈接：https://blog.csdn.net/cxhply/article/details/49423501
總結
以上是生活随笔為你收集整理的[Leedcode][JAVA][第209题][长度最小的子数组][滑动窗口][前缀和][二分查找][双指针]的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
