配列の検索および演算テクニック

配列は連続したメモリ領域を使用する基本的なコレクションであり、インデックスによる高速アクセスが可能です。ここでは、配列を扱う際の代表的なアルゴリズムパターンとその実装について解説します。

1. 二分探索アルゴリズムの境界条件

ソートされた配列から特定の値を検索する際に、二分探索法が用いられます。実装上の注意点として、探索範囲（インターバル）の定義方法によって終了条件が異なります。

• 閉区間 [left, right]: 範囲に含まれる場合、終了判定は left <= right となります。
• 半開区間 [left, right): 右端が含まれない場合、終了判定は left < right とし、更新時には mid を含むかどうかを慎重に処理する必要があります。

以下のコードは、再帰呼び出しおよび反復処理による実装例です。

#include <vector>
#include <climits>
using namespace std;

// 再帰方式による探索
int recursiveSearch(const vector<int>& data, int target, int left, int right) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    if (data[mid] == target) return mid;
    
    if (data[mid] > target) {
        return recursiveSearch(data, target, left, mid - 1);
    } else {
        return recursiveSearch(data, target, mid + 1, right);
    }
}

// 非再帰方式（闭区间）
int iterativeSearchClosed(const vector<int>& data, int target) {
    int left = 0;
    int right = static_cast<int>(data.size()) - 1;
    
    while (left <= right) {
        int mid = left + ((right - left) >> 1); // ビットシフトによる除算
        
        if (data[mid] == target) {
            return mid;
        } else if (data[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

// 非再帰方式（半開区間）
int iterativeSearchOpen(const vector<int>& data, int target) {
    int left = 0;
    int right = static_cast<int>(data.size()); 
    
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        
        if (data[mid] == target) return mid;
        
        if (data[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

2. インプレースでの要素除去（双ポインタ法）

配列から特定の条件を満たさない要素を削除する場合、要素のシフト作業が発生します。メモリ効率を考慮し、追加のバッファを使わずに行うためには、書き込み用と読み込み用のポインタ（インデックス）を使い分ける手法が有効です。

LeetCode 27: 指定値の除去

int removeSpecificValue(vector<int>& nums, int valToRemove) {
    int writeIndex = 0;
    
    for (int readIndex = 0; readIndex < static_cast<int>(nums.size()); ++readIndex) {
        if (nums[readIndex] != valToRemove) {
            nums[writeIndex++] = nums[readIndex];
        }
    }
    
    return writeIndex;
}

3. スライディングウィンドウ技法

連続するサブアレイやサブストリングの問題において、重なり合う部分集合に対して計算を行う際、二重ループではなく単一のループで処理可能にする最適化手法です。

アルゴリズムのロジック

1. ウィンドウ拡張: 右端ポインタを移動させ、新しい要素を追加します。
2. 条件確認: ウィンドウ内の状態が目標条件を満たすか判断します。
3. ウィンドウ収縮: 条件を満たした場合、左端ポインタを移動させて不要な要素を取り除き、結果を更新しながら最小規模などを求めます。

LeetCode 209: 合計値以上の最短部分配列

int minSubArrayLength(int target, vector<int>& nums) {
    int minLength = INT_MAX;
    int currentSum = 0;
    int left = 0;
    int n = static_cast<int>(nums.size());
    
    for (int right = 0; right < n; ++right) {
        currentSum += nums[right];
        
        // 条件を満たす限り左側から縮小
        while (currentSum >= target) {
            int len = right - left + 1;
            if (len < minLength) {
                minLength = len;
            }
            currentSum -= nums[left];
            left++;
        }
    }
    
    return (minLength == INT_MAX) ? 0 : minLength;
}

4. 二次元配列の境界シミュレーション

矩阵の螺旋順序（スパイラル順）に従って数字を割り当てる問題は、境界条件を厳密に管理する必要があります。上・下・左・右の各境界線を持ちながら、移動方向を変更して充填していくアプローチを取ります。

LeetCode 59: スパイラルマトリクス生成

vector<vector<int>> createSpiralMatrix(int dimension) {
    vector<vector<int>> grid(dimension, vector<int>(dimension));
    int num = 1;
    
    int top = 0;
    int bottom = dimension - 1;
    int left = 0;
    int right = dimension - 1;
    
    while (top <= bottom && left <= right) {
        // 上辺：左から右へ
        for (int i = left; i <= right; ++i) grid[top][i] = num++;
        top++;
        
        // 右辺：上から下へ
        for (int i = top; i <= bottom; ++i) grid[i][right] = num++;
        right--;
        
        // 下辺：右から左へ
        if (top <= bottom) {
            for (int i = right; i >= left; --i) grid[bottom][i] = num++;
            bottom--;
        }
        
        // 左辺：下から上へ
        if (left <= right) {
            for (int i = bottom; i >= top; --i) grid[i][left] = num++;
            left++;
        }
    }
    
    return grid;
}