Problem#
給你一個正整數陣列 nums
和一個正整數 target
,要求 subarray 總和不超過 target
,要你回傳 subarray 最小的長度,如果找不到則回傳 0
測資限制#
- $1 \le target \le 10^9$
- $1 \le nums \le 10^5$
- $1 \le nums[i] \le 10^4$$
想法#
求 subarray 總和,雙指標
能往右就盡量往右,直到 sum >= target
開始縮減左界(往右長)直到 sum < target
又開始增長右界
每次移動 左界(i
)、右界(j
) 時去看有沒有 sum >= target
有的話找最小的 j-i+1
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$
AC Code#
TODO: O(nlogn)
解法