python - 線形時間で合計 >= k の n 個の整数の最小部分配列を見つける

Question

最近、私は次の問題に苦労しています。

与えられた整数の配列から、合計が少なくとも k になる最小 (最短の長さ) の部分配列を見つけます。

明らかに、これは O(n^2) で簡単に実行できます。自然数については線形時間で解くアルゴリズムを書くことができましたが、整数についてはわかりません。

私の最近の試みはこれでした：

def find_minimal_length_subarr_z(arr, min_sum):
    found = False
    start = end = cur_end = cur_sum = 0
    for cur_start in range(len(arr)):
        if cur_end <= cur_start:
            cur_end, cur_sum = cur_start, arr[cur_start]
        else:
            cur_sum -= arr[cur_start-1]
        # Expand
        while cur_sum < min_sum and cur_end < len(arr)-1:
            cur_end += 1
            cur_sum += arr[cur_end]
        # Contract
        while cur_end > cur_start:
            new_sum = cur_sum - arr[cur_end]
            if new_sum >= min_sum or new_sum >= cur_sum:
                cur_end -= 1
                cur_sum = new_sum
            else:
                break
        if cur_sum >= min_sum and (not found or cur_end-cur_start < end-start):
            start, end, found = cur_start, cur_end, True
    if found:
        return start, end

例えば：

[8, -7, 5, 5, 4], 12 => (2, 4)

ただし、次の場合は失敗します。

[-12, 2, 2, -12, 2, 0], 4

正しい結果が得(1, 2)られますが、アルゴリズムはそれを見つけられません。

これを線形時間で行うことはできますか (空間の複雑さが一定であることが望ましい)?