題目
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
解法思路
- 從數(shù)組的起始處撐開一個(gè)滑動(dòng)窗口；
- 以目標(biāo)值
s和窗口的值windowLength的大小關(guān)系作為窗口拉長和縮短的依據(jù)； - 在窗口拉長和縮短的過程中，維護(hù)窗口的值
windowSum和長度windowLength； - 在每次窗口的長度發(fā)生變化后，檢查窗口的值
windowSum是否 >=s時(shí)，并在滿足條件的情況下判斷是否出現(xiàn)了更短的窗口；
時(shí)間復(fù)雜度
- O(N)；
關(guān)鍵詞
滑動(dòng)窗口 數(shù)組 雙指針 二分查找
算法實(shí)現(xiàn)
-
l和r表示窗口的左右邊界； - 窗口完全滑出數(shù)組的情況是：
l < nums.length； - 注意窗口的右邊界
r在滑動(dòng)的時(shí)候不能超過數(shù)組的右邊界；
package leetcode._209;
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int l = 0, r = -1;
int windowSum = 0;
int windowLength = nums.length + 1;
while (l < nums.length) {
if (r + 1 < nums.length && windowSum < s) {
r++;
windowSum += nums[r];
} else {
windowSum -= nums[l];
l++;
}
if (windowSum >= s) {
windowLength = Math.min(windowLength, (r - l + 1));
}
}
if (windowLength == nums.length + 1) {
return 0;
}
return windowLength;
}
public static void main(String[] args) {
int[] arr = {2, 3, 1, 2, 4, 3};
int windowLength = (new Solution()).minSubArrayLen(7, arr);
System.out.println(windowLength);
}
}
