総和がtarget以上になるような最小の部分列の長さを求める問題。
公式の最適解は2 pointersで、O(N)で解ける。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
ans = float('inf')
l = 0
val = 0
for i in range(n):
val += nums[i]
while val >= target:
ans = min(ans, i - l + 1)
val -= nums[l]
l += 1
if ans == float('inf'):
ans = 0
return ans別解がいくつかあるので、考えてみる。
尺取り法
forループを使わない2 pointersに近い。
全ての要素を1度見れば済むので、時間計算量はO(N)。
ポインタと答えを保存する変数しか使わないので、空間計算量はO(1)。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if sum(nums) < target:
return 0
n = len(nums)
l = -1
r = -1
curr = 0
ans = float('inf')
while r < n:
if l > r:
r = l
curr = 0
continue
if curr < target:
r += 1
if r >= n:
break
curr += nums[r]
else:
l += 1
curr -= nums[l]
ans = min(ans, r - l + 1)
if ans == float('inf'):
ans = 0
return ans部分和がtargetより小さければrightを進め、大きければleftを進める。
left が right を追い越したらリセット。
if l > r:
r = l
curr = 0
continueポインタの初期値を-1にすることで、「今いる場所までの和」の計算が楽になる。
0スタートにすると、足し引きしてからポインタを進める→長さの計算という流れになり、r-l+1ではなくなって直感に反する。
if curr < target:
r += 1
if r >= n:
break
curr += nums[r]
else:
l += 1
curr -= nums[l]
ans = min(ans, r - l + 1)累積和
部分和の問題は累積和を取ることで計算量を落とせることが多い。
今回の問題も累積和をあらかじめ計算してから全探索することで計算量をO(n^3)からO(N^2)に落とすことが出来る。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
cumsum = [0] * (n + 1)
for i in range(1, n + 1):
cumsum[i] = cumsum[i - 1] + nums[i - 1]
ans = float('inf')
for i in range(n + 1):
for j in range(i, n + 1):
val = cumsum[j] - cumsum[i]
if val >= target:
ans = min(ans, j - i)
if ans == float('inf'):
ans = 0
return ans二分探索
制約条件から与えられる配列は正の値のみからなるので、累積和は単調増加となる。
累積和をソート済みの配列だと考えると、二分探索を使うことができそう。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
cumsum = [0] * (n + 1)
for i in range(1, n + 1):
cumsum[i] = cumsum[i - 1] + nums[i - 1]
ans = float('inf')
for i in range(n, -1, -1):
if cumsum[i] < target:
break
l = -1
r = i + 1
while r - l > 1:
mid = (l + r) // 2
if cumsum[i] - cumsum[mid] >= target:
l = mid
else:
r = mid
ans = min(ans, i - l)
if ans == float('inf'):
ans = 0
return ans累積和がtarget以下の場合、部分和もtarget以下になる。
途中で処理を打ち切ると定数倍高速化できるので、forループは逆順で回す。
for i in range(n, -1, -1):
if cumsum[i] < target:
breakめぐる式二分探索を行う。
求める答えは最小の長さなので、部分和がtarget以上になるような最大のleftを探せば良い。
累積和と使った部分和の長さはr-l+1ではなくr-lなのに注意。
l = -1
r = i + 1
while r - l > 1:
mid = (l + r) // 2
if cumsum[i] - cumsum[mid] >= target:
l = mid
else:
r = mid
ans = min(ans, i - l)
前処理の累積和の計算がO(N)、メインの二分探索＋ループがO(N logN)となり、遅い方のO(N logN)が時間計算量。
空間計算量は累積和の配列を用意するためO(N)。
最適解ではないが、累積和をソート済み配列だと考えるのが面白かった。
コメント