PrefixSum, Sliding Window

## 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 + スライディングウィンドウ）

```java
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;
    }
}
```

### コード解説

1. **Prefix Sum 配列の構築**  
   - `prefixSum[i] = prefixSum[i - 1] + nums[i - 1]`  
   - これにより、`[l, r]` の区間和を  
     ```
     {prefixSum}[r + 1] - {prefixSum}[l]
     ```
     の形で瞬時（\(O(1)\)）に取得できます。

2. **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` が最終要素を越えたらループ終了

3. **結果**  
   - `ans` が更新されないままなら `Integer.MAX_VALUE` のままなので 0 を返す  
   - 更新されていれば、最終的に求まった最小長を返す

---

### 動作の一例

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

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

---

## 5. 他の解法（参考）

- **スライディングウィンドウ（Two Pointer）: 累積和を使わない方法**  
  ```java
  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)\)

---

## まとめ

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