PrefixSum, Sliding Window

Posted at 2025-01-21

1. Prefix Sum（累積和）の概念

Prefix Sum（累積和）は、配列の区間和を高速（通常 (O(1)) 時間）で求めるための手法です。

一般的に prefixSum[0] = 0 とし、
prefixSum[i] = prefixSum[i - 1] + nums[i - 1]（i を 1 から始める場合）
という形で計算します。

こうすることで、インデックス (L) から (R) までの区間和は

{prefixSum}[R + 1] - {prefixSum}[L]

で (O(1)) 時間に求めることができます。

例えば、

nums = [2, 3, 1, 2, 4, 3]
prefixSum = [0, 2, 5, 6, 8, 12, 15]

prefixSum[1] = 2 (nums[0] = 2)
prefixSum[2] = 5 (nums[0] + nums[1] = 2 + 3)
…
prefixSum[6] = 15 (2 + 3 + 1 + 2 + 4 + 3)

区間 [1, 3] の和は

prefixSum[4] - prefixSum[1] = 8 - 2 = 6

となります。

2. スライディングウィンドウ（Two Pointer）の概念

スライディングウィンドウは、配列（もしくはリスト）における連続する部分配列（subarray）を扱う際に、多くの問題を効率的に解くためによく利用されるテクニックです。

ふつう、左端ポインタ（left）と右端ポインタ（right）という 2 つのポインタを用い、現在扱っているウィンドウを [left, right] で表現します。
right を右に動かしてウィンドウを拡張し、目的の条件（例：区間和がある値以上になるなど）を満たしたら、left を動かしてウィンドウを縮めつつ最適解（例：最小長）を探します。
配列内の要素が すべて正の整数 である場合は、区間和が大きくなった際に left を進めて調整する手法がシンプルに適用できます（要素に負数が含まれると単純な Two Pointer では対応しにくいです）。

3. LeetCode 209番問題（例）

問題要約
正の整数のみからなる配列 nums が与えられ、部分配列（連続する要素列）の和が target 以上となるような最小の長さを求める。そうした部分配列が存在しない場合は 0 を返す。

例:

nums = [2, 3, 1, 2, 4, 3], target = 7 → 答えは 2（部分配列 [4,3] などが合計 7）

4. 提示されたコード（Prefix Sum + スライディングウィンドウ）

import java.util.*;

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int size = nums.length + 1;
        int[] prefixSum = new int[size];

        // 1) prefixSum の計算
        for(int i = 1; i < size; i++){
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }

        // 2) Two Pointer（スライディングウィンドウ）の初期化
        int left = 0;
        int right = 0;
        int ans = Integer.MAX_VALUE;

        // 3) [left, right] 区間の和を、prefixSum を使って O(1) で算出
        while(right <= nums.length - 1){
            int sum = prefixSum[right + 1] - prefixSum[left];

            if(sum < target){
                // 目標値未満であれば、ウィンドウを拡張（right を右へ移動）
                right++;
            } else {
                // 目標値以上であれば、
                //  - 現在のウィンドウ長で ans を更新
                //  - ウィンドウを縮めてより小さい長さを探すため left を進める
                ans = Math.min(ans, right - left + 1);
                left++;
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

コード解説

Prefix Sum 配列の構築
- prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
- これにより、[l, r] の区間和を
```
{prefixSum}[r + 1] - {prefixSum}[l]
```
  の形で瞬時（(O(1))）に取得できます。
Two Pointer（スライディングウィンドウ）の開始
- left = 0, right = 0 で初期化
- while (right <= nums.length - 1) のループ内で:
  - sum = prefixSum[right + 1] - prefixSum[left] を計算
  - sum < target なら right++ → ウィンドウ拡張
  - sum >= target なら
    - 現在のウィンドウ長（right - left + 1）で ans を更新
    - left++ → ウィンドウを縮めてもっと短い区間が可能か探る
- 右端 right が最終要素を越えたらループ終了
結果
- ans が更新されないままなら Integer.MAX_VALUE のままなので 0 を返す
- 更新されていれば、最終的に求まった最小長を返す

動作の一例

例: target = 7, nums = [2, 3, 1, 2, 4, 3]

prefixSum = [0, 2, 5, 6, 8, 12, 15]
はじめは left = 0, right = 0
- sum = prefixSum[1] - prefixSum[0] = 2 → 2 < 7 なので right++
left = 0, right = 1
- sum = prefixSum[2] - prefixSum[0] = 5 → 5 < 7 なので right++
left = 0, right = 2
- sum = prefixSum[3] - prefixSum[0] = 6 → 6 < 7 なので right++
left = 0, right = 3
- sum = prefixSum[4] - prefixSum[0] = 8 → 8 >= 7
- ans = 4（ウィンドウ [0,3] の長さ）
- left++ → left = 1
left = 1, right = 3
- sum = prefixSum[4] - prefixSum[1] = 8 - 2 = 6 → 6 < 7 なので right++
… という具合に進め、最終的に ans が 2（例: [4,3] など）に更新されます。

5. 他の解法（参考）

スライディングウィンドウ（Two Pointer）: 累積和を使わない方法

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0;
    int ans = Integer.MAX_VALUE;

    for(int right = 0; right < nums.length; right++){
        sum += nums[right];
        while(sum >= target){
            ans = Math.min(ans, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

毎回 nums[right] を加算し、sum >= target の間は left++ しながら最小長を求める。
prefixSum 配列なしでも同様の処理ができ、実装もややシンプル。

Prefix Sum + 二分探索
- 累積和配列は単調増加（要素が正の整数のみ）になるため、
- あるインデックス i に対して「prefixSum[j] >= prefixSum[i] + target を満たす最小の j」を二分探索するやり方
- 計算量は (O(n \log n))

まとめ

Prefix Sum は区間和を瞬時に計算するための代表的な手法。
スライディングウィンドウ（Two Pointer） は、連続部分配列の問題（特に要素がすべて正のとき）で効率的に最適解を探すアプローチ。
今回のコードは、Prefix Sum + スライディングウィンドウ を組み合わせて、区間和を即時に求めつつ、sum >= target ならウィンドウを縮めて最短長を更新し、sum < target ならウィンドウを広げるという流れを実装している。
同じ問題を必ずしも prefixSum で解く必要はなく、スライディングウィンドウ単独でも解ける。
しかし Prefix Sum を併用することで、sum = prefixSum[r + 1] - prefixSum[l] と明示的に区間和を求められるため、コードとして分かりやすくなる場合がある。
配列に負の数が含まれると、こうした単純な Two Pointer では解きにくいので、別の手法（またはアルゴリズムの修正）が必要となることが多い。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up