LeetCode 977. 平方済みソート済み配列

この問題では、昇順にソートされた整数配列が与えられたとき、各要素を二乗した後の配列も昇順になるような新しい配列を作成します。配列の両端から中央に向かって比較しながら埋めていく手法が有効です。

実装上の注意点：

• 結果用の新しい配列を明示的に確保し、そこに値を埋めていく方式を採用すること
• 配列の末尾から順に値を挿入していくため、挿入位置を追跡する専用のインデックス変数を設けると実装がシンプルになる

public int[] sortedSquares(int[] nums) {
    int start = 0;
    int end = nums.length - 1;
    int position = nums.length - 1;
    int[] result = new int[nums.length];

    while (start <= end) {
        int leftSquare = nums[start] * nums[start];
        int rightSquare = nums[end] * nums[end];
        
        if (leftSquare > rightSquare) {
            result[position] = leftSquare;
            position--;
            start++;
        } else {
            result[position] = rightSquare;
            position--;
            end--;
        }
    }

    return result;
}

LeetCode 209. 最短部分配列長

連続する部分配列のうち、その要素の合計がtarget以上となるもののうち最短の長さを見つける問題です。滑动窓（スライディングウィンドウ）アルゴリズムの典型的な適用例となります。

実装上のポイント：

• 窓の拡張条件と縮小条件を明確に区別すること。この問題では合計値がtargetに達した時点で縮小処理を開始できる
• 窓の拡大処理では、rightポインタが指す要素を加算してからrightをインクリメントする顺序が重要
• テンプレートパターンを理解し、自分の言葉で説明できるレベルまで習熟すること

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

    while (right < nums.length) {
        // 窓を拡大
        sum += nums[right];
        right++;

        // 窓を縮小しながら条件を満たすかチェック
        while (sum >= target) {
            minLength = Math.min(minLength, right - left);
            sum -= nums[left];
            left++;
        }
    }

    return minLength == Integer.MAX_VALUE ? -1 : minLength;
}

LeetCode 59. スpiral行列 II

1からn²までの数値を時計回りにスパイラル状に埋めたn×n行列を生成する問題です。境界値を管理する四つの変数upper、lower、left、rightを用いて、一圈ずつ値を埋めていくのが標準的なアプローチです。

実装上のポイント：

• 境界条件を満たす場合のみ対応する方向的ループを実行する
• 一圈終わるごとに四つの境界を更新し、次の圈に備える
• 差分配列や境界管理等、他分野との知識接続を意識して复习すること

public int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    int top = 0, bottom = n - 1;
    int left = 0, right = n - 1;
    int value = 1;
    
    while (value <= n * n) {
        // 上辺：左から右へ
        if (top <= bottom) {
            for (int j = left; j <= right; j++) {
                matrix[top][j] = value++;
            }
            top++;
        }
        
        // 右辺：上から下へ
        if (left <= right) {
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = value++;
            }
            right--;
        }
        
        // 下辺：右から左へ
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                matrix[bottom][j] = value++;
            }
            bottom--;
        }
        
        // 左辺：下から上へ
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = value++;
            }
            left++;
        }
    }
    return matrix;
}