配列の基礎特性について
配列は、連続したメモリ領域に同種型のデータ要素を格納するデータ構造です。以下の性質を理解することが重要です：
- インデックス付けは通常 0 から始まります。
- 物理的なメモリアドレスは隣接しています。
- std::vector と従来の配列（array）の違い：vector は動的配列であり、内部でアレイ管理を行いますが、厳密にはコンテナクラスとして機能します。
- 配列内の既存要素を削除することはできません。代わりに値を上書きして論理的に減少させる処理が必要です。
- C++ の多次元配列も連続メモリ上に配置されます。
二分探索アルゴリズム
ソート済みのデータセットにおいて、対象要素を見つけるための効率的な手法です。区間の閉じ方（左閉右開か左閉右閉か）を統一するとバグを防ぎやすくなります。
標準的な二分探索
与えられたキーが配列に含まれているかどうかを確認し、存在位置を返す処理です。
class Solution {
public:
int findPosition(std::vector<int>& input_arr, int search_key) {
int ptr_start = 0;
int ptr_end = static_cast<int>(input_arr.size()) - 1;
while (ptr_start <= ptr_end) {
// オーバーフロー防止のため計算式を変更
int mid = ptr_start + ((ptr_end - ptr_start) / 2);
if (search_key < input_arr[mid]) {
ptr_end = mid - 1;
} else if (input_arr[mid] < search_key) {
ptr_start = mid + 1;
} else {
return mid;
}
}
return -1;
}
};挿入位置の特定
キーが存在しない場合、どのような順序で挿入すべき位置（インデックス）を計算します。条件判定時に現在の最小候補を記録することで対応できます。
class Solution {
public:
int locateInsertPoint(std::vector<int>& input_arr, int target_val) {
int idx_left = 0;
int idx_right = static_cast<int>(input_arr.size()) - 1;
int potential_pos = static_cast<int>(input_arr.size());
while (idx_left <= idx_right) {
int pivot = (idx_left + idx_right) / 2;
if (input_arr[pivot] >= target_val) {
potential_pos = pivot;
idx_right = pivot - 1;
} else {
idx_left = pivot + 1;
}
}
return potential_pos;
}
};範囲の特定（左端・右端）
同一値が複数出現する場合、その開始点と終了点を検索するには、左右それぞれに二分探索を実行する必要があります。終了条件や境界更新ロジックに注意してください。
class Solution {
public:
std::vector<int> findRange(std::vector<int>& arr, int target_val) {
int border_left = getLeftBound(arr, target_val);
int border_right = getRightBound(arr, target_val);
if (border_left == -2 || border_right == -2 || (border_right - border_left) > 1) {
return {-1, -1};
}
return {border_left + 1, border_right - 1};
}
private:
int getLeftBound(std::vector<int>& arr, int target) {
int l = 0, r = static_cast<int>(arr.size()) - 1;
int bound = -2;
while (l <= r) {
int m = l + ((r - l) / 2);
if (arr[m] < target) {
l = m + 1;
} else {
r = m - 1;
bound = r;
}
}
return bound;
}
int getRightBound(std::vector<int>& arr, int target) {
int l = 0, r = static_cast<int>(arr.size()) - 1;
int bound = -2;
while (l <= r) {
int m = l + ((r - l) / 2);
if (arr[m] > target) {
r = m - 1;
} else {
l = m + 1;
bound = l;
}
}
return bound;
}
};二重ポインタ法（Remove & Swap）**
一度で走査しながら複数の目的を達成できる技法です。「読み取り用ポインタ」と「書き込み用ポインタ」を運用します。
特定値の除去
指定値以外の要素のみを残し、新しい長さを返します。
class Solution {
public:
int removeTarget(std::vector<int>& nums, int val) {
int write_idx = 0;
for (int read_idx = 0; read_idx < nums.size(); ++read_idx) {
if (nums[read_idx] != val) {
nums[write_idx++] = nums[read_idx];
}
}
return write_idx;
}
};重複项の削除
ソート済み配列から重複を除き、先頭からの重複のない部分を構築します。
class Solution {
public:
int uniqueCount(std::vector<int>& nums) {
if (nums.empty()) return 0;
int slow = 0;
for (int fast = 1; fast < nums.size(); ++fast) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
};ゼロの移動
ゼロ以外の値を前方へ押し出し、残りをゼロで埋めます。
class Solution {
public:
void moveZeroes(std::vector<int>& nums) {
int slow_ptr = 0;
// まずゼロ以外を前に集める
for (int fast_ptr = 0; fast_ptr < nums.size(); ++fast_ptr) {
if (nums[fast_ptr] != 0) {
nums[slow_ptr++] = nums[fast_ptr];
}
}
// 後ろ側をゼロで埋める
while (slow_ptr < nums.size()) {
nums[slow_ptr++] = 0;
}
}
};文字列比較（バックスペース処理を含む）
末尾から逆走して '#' をカウントし、該当箇所をスキップさせてから比較します。
class Solution {
public:
bool verifyBackspaceStrings(std::string s, std::string t) {
int skip_s = 0, skip_t = 0;
int i = static_cast<int>(s.length()) - 1;
int j = static_cast<int>(t.length()) - 1;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (s[i] == '#') { skip_s++; i--; }
else {
if (skip_s > 0) { skip_s--; i--; }
else break;
}
}
while (j >= 0) {
if (t[j] == '#') { skip_t++; j--; }
else {
if (skip_t > 0) { skip_t--; j--; }
else break;
}
}
if (i >= 0 && j >= 0 && s[i] != t[j]) return false;
i--; j--;
}
return (i == -1 && j == -1);
}
};ソート配列の平方和
負の数を含む場合、単純な二乗では順序が変わります。両端から比較して大きい順に結果配列に詰めるアプローチが効果的です。
class Solution {
public:
std::vector<int> sortedSquared(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> result(n);
int left = 0, right = n - 1;
int pos = n - 1;
while (left <= right) {
long sq_l = (long)nums[left] * nums[left];
long sq_r = (long)nums[right] * nums[right];
if (sq_l < sq_r) {
result[pos--] = (int)sq_r;
right--;
} else {
result[pos--] = (int)sq_l;
left++;
}
}
return result;
}
};スライディングウィンドウ技術
固定サイズまたは可変サイズの範囲を滑動させながら特定の条件を満たす部分列を見つけます。
最小長さのサブ配列
和が指定値以上になる最短の連続部分列の長さを求めます。
class Solution {
public:
int minLengthSum(int target, std::vector<int>& nums) {
int total_sum = 0;
int min_len = std::numeric_limits<int>::max();
int start = 0;
for (int end = 0; end < nums.size(); ++end) {
total_sum += nums[end];
while (total_sum >= target) {
int current_len = end - start + 1;
if (current_len < min_len) {
min_len = current_len;
}
total_sum -= nums[start];
start++;
}
}
return (min_len == std::numeric_limits<int>::max()) ? 0 : min_len;
}
};フルーツバスケット
2 つ以上の異なるタイプしか持てない場合、最大で収穫可能な果物の数を得る問題です。ウィンドウの端を調整します。
class Solution {
public:
int maxBasketSize(std::vector<int>& fruits) {
if (fruits.empty()) return 0;
int left = 0;
int ans = 0;
// ハッシュマップを使用して頻度を管理するのが一般的ですが、
// 2 種類制約の場合は以下のような簡易ロジックも可能です
int type_a = fruits[0], count_a = 0;
int type_b = fruits[0], count_b = 0;
for (int right = 0; right < fruits.size(); ++right) {
if (fruits[right] == type_a || fruits[right] == type_b) {
ans = std::max(ans, right - left + 1);
} else {
// 3 種類目が出现したら、直前の連続部分を保持しつつ更新
// ここで複雑化するので基本的な実装では
// 最も近い左端まで縮小し、タイプを切り替える
// この部分は問題仕様に依存するため一般的な実装例
// 実際のコードでは map/vector を使用し、count を管理するのが推奨されます
}
}
return ans;
}
};※上記フルーツ成篮の問題は、本質的に「最多出現回数のサブストリング」または「最長の部分文字列（異なる文字数制限）」に帰着されることが多く、実務的にはハッシュマップや Counter を用いて状態管理を行う実装が望ましいです。
行列の螺旋走査と生成
二次元配列における方向転換ループです。「左閉右開」などの不変条件を維持し、外側から内側へ向かってループ回数を減らしていくのが定石です。
螺旋行列の生成
n x n の行列に 1 から順に数字を埋めます。
class Solution {
public:
std::vector<std::vector<int>> generateSpiralMatrix(int n) {
std::vector<std::vector<int>> grid(n, std::vector<int>(n, 0));
int start_x = 0, start_y = 0;
int loop_count = n / 2;
int offset = 1;
int count = 1;
while (loop_count--) {
int i = start_x, j = start_y;
// 上辺（左から右へ）
for (; j < n - offset; j++) {
grid[i][j] = count++;
}
// 右辺（上から下へ）
for (; i < n - offset; i++) {
grid[i][j] = count++;
}
// 下辺（右から左へ）
for (; j > start_y; j--) {
grid[i][j] = count++;
}
// 左辺（下から上へ）
for (; i > start_x; i--) {
grid[i][j] = count++;
}
start_x++;
start_y++;
offset++;
}
// 奇数次の場合、中央点を埋める
if (n % 2) {
grid[n / 2][n / 2] = count;
}
return grid;
}
};螺旋行列の走査
既に作成された行列から螺旋状に要素を読み取ります。行数和列数が異なる場合、最小辺の半分でループを回し、残りの部分を処理する必要があります。
class Solution {
public:
std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return {};
std::vector<int> result;
int rows = matrix.size();
int cols = matrix[0].size();
int start_x = 0, start_y = 0;
int loops = std::min(rows, cols) / 2;
int offset = 1;
while (loops--) {
int i = start_x, j = start_y;
// 右へ
for (; j < cols - offset; j++) result.push_back(matrix[i][j]);
// 下へ
for (; i < rows - offset; i++) result.push_back(matrix[i][j]);
// 左へ
for (; j > start_y; j--) result.push_back(matrix[i][j]);
// 上へ
for (; i > start_x; i--) result.push_back(matrix[i][j]);
start_x++; start_y++; offset++;
}
// 残りの要素処理（奇数時）
if (rows > cols) {
for (int i = rows / 2; i < (cols + rows + 1) / 2; i++) {
result.push_back(matrix[i][start_y]);
}
} else if (cols > rows) {
for (int j = cols / 2; j < (rows + cols + 1) / 2; j++) {
result.push_back(matrix[start_x][j]);
}
} else if (rows == cols && rows % 2) {
result.push_back(matrix[rows/2][cols/2]);
}
return result;
}
};