Leetcode 209 - Minimum Size Subarray Sum

題目

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) 解法