LeetCodeの代表的なアルゴリズム問題とその解答

LeetCodeの代表的なアルゴリズム問題とそのC++による実装をまとめました。文字列、配列、連結リスト、動的計画法などのトピックを取り上げ、アルゴリズム面接準備や日頃の練習に役立ちます。

目次

  1. 文字列処理
  2. 配列問題
  3. 連結リスト操作
  4. 動的計画法
  5. 木の走査

1. 文字列処理

1.1 二進数の部分文字列を数える（Count Binary Substrings）

問題説明：与えられた文字列において、連続した0と1の数が同じ部分文字列の数を求める。

解法の概要：

  • 連続する同じ文字のグループの長さを記録
  • 隣接する2つのグループから作れる部分文字列数は、それぞれの長さの最小値
  • 例：「00111」はグループ[2,3]となり、min(2,3)=2個の部分文字列を作れる

実装コード：

int countBinarySubstrings(string s) {
    vector<int> groups;
    s += ' ';
    int size = s.size();
    int count = 0;
    
    for (int i = 0; i < size - 1; i++) {
        if (s[i] == s[i + 1]) {
            count++;
        } else {
            count++;
            groups.push_back(count);
            count = 0;
        }
    }
    
    int result = 0;
    for (int i = 1; i < groups.size(); i++) {
        result += min(groups[i-1], groups[i]);
    }
    return result;
}

時間計算量：O(n) 空間計算量：O(n)

1.2 重複しない最長部分文字列（Longest Substring Without Repeating Characters）

問題説明：与えられた文字列の中で、重複しない文字を含む最長部分文字列の長さを求める。

解法の概要：

  • スライディングウィンドウ＋ハッシュセットを使用
  • 右側のポインタを広げて、重複文字に出会ったら左側を縮める
  • 最大のウィンドウ長を維持

実装コード：

#include <unordered_set>
#include <algorithm>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set<char> seen;
    int left = 0, right = 0;
    int maxLength = 0;

    while (right < s.size()) {
        if (seen.count(s[right]) == 0) {
            seen.insert(s[right]);
            maxLength = max(maxLength, right - left + 1);
            right++;
        } else {
            seen.erase(s[left]);
            left++;
        }
    }
    return maxLength;
}

時間計算量：O(n) 空間計算量：O(min(n, m))（mは文字集合のサイズ）

1.3 最長回文部分文字列（Longest Palindromic Substring）

問題説明：文字列の中で最も長い回文部分文字列を求める。

解法の概要：

  • 中心拡張法：各文字を基準として両側へ展開
  • 奇数長と偶数長の両方を考慮
  • 最長回文の開始位置と長さを記録

実装コード：

string longestPalindrome(string s) {
    int start = 0, end = 0;
    int length = 0;
    int pos = 0;
    
    for (int i = 0; i < s.size() - 1; i++) {
        // 奇数長の回文
        int l = i, r = i;
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--;
            r++;
        }
        if (r - l - 2 > length) {
            length = r - l - 1;
            pos = l + 1;
        }
        
        // 偶数長の回文
        l = i;
        r = i + 1;
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--;
            r++;
        }
        if (r - l - 2 > length) {
            length = r - l - 1;
            pos = l + 1;
        }
    }
    return s.substr(pos, length);
}

時間計算量：O(n²) 空間計算量：O(1)

2. 配列問題

2.1 2数の和（Two Sum）

問題説明：配列内で合計が目標値になる2つの数を見つける。

解法の概要：

  • ハッシュマップに既に訪れた数値とインデックスを格納
  • 現在の数に対して、target - nums[i]が存在するか確認
  • 1回のループで完了

実装コード：

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        if (map.find(target - nums[i]) != map.end()) {
            return {map[target - nums[i]], i};
        } else {
            map[nums[i]] = i;
        }
    }
    return {};
}

時間計算量：O(n) 空間計算量：O(n)

2.2 3数の和（Three Sum）

問題説明：配列内で合計が0になる3つの要素の組み合わせをすべて求める。

解法の概要：

  • 配列をソート
  • 1つ目を固定し、残り2つを2つのポインタで探す
  • 重複を避けるためにスキップ処理を行う

実装コード：

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    
    for (int i = 0; i < n; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = n - 1;
        int target = -nums[i];
        
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                result.push_back({nums[i], nums[left], nums[right]});
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;
                while (left < right && nums[right] == nums[right + 1]) right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

時間計算量：O(n²) 空間計算量：O(1)（結果を除く）

2.3 最大部分配列和（Maximum Subarray）

問題説明：配列の中で合計が最大になる連続部分配列を見つける。

方法1：動的計画法（Kadaneアルゴリズム）

解法の概要：

  • dp[i]はnums[i]で終わる最大部分配列和
  • 状態遷移：dp[i] = max(nums[i], dp[i-1] + nums[i])
  • 空間をO(1)に最適化可能

実装コード：

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int prev = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        prev = (prev + nums[i] < nums[i]) ? nums[i] : prev + nums[i];
        maxSum = (maxSum > prev) ? maxSum : prev;
    }
    return maxSum;
}

時間計算量：O(n) 空間計算量：O(1)

方法2：分割統治法

解法の概要：

  • 配列を左右に分割
  • 最大部分配列は左側、右側、中央を跨ぐのいずれか
  • 再帰的に求めてマージ

実装コード：

struct Status {
    int lSum;
    int rSum;
    int iSum;
    int mSum;
};

Status get(vector<int>& a, int l, int r) {
    if (l == r) {
        return (Status){a[l], a[l], a[l], a[l]};
    }
    int m = (l + r) >> 1;
    Status left = get(a, l, m);
    Status right = get(a, m + 1, r);
    
    int iSum = left.iSum + right.iSum;
    int lSum = max(left.lSum, left.iSum + right.lSum);
    int rSum = max(right.rSum, right.iSum + left.rSum);
    int mSum = max(max(left.mSum, right.mSum), left.rSum + right.lSum);
    
    return (Status){lSum, rSum, iSum, mSum};
}

int maxSubArray(vector<int>& nums) {
    return get(nums, 0, nums.size() - 1).mSum;
}

時間計算量：O(n log n) 空間計算量：O(log n)

2.4 K番目の要素（Kth Largest Element）

問題説明：配列内でK番目に大きい要素を見つける。

解法の概要：

  • ランダム選択法（Quick Select）を使用
  • K番目は(n-K)番目小さい要素に相当
  • 完全なソートは必要なく、partition操作のみでOK

実装コード：

int partition(vector<int>& nums, int l, int r) {
    int pivot = nums[r];
    int i = l;
    
    for (int j = l; j < r; ++j) {
        if (nums[j] < pivot) {
            swap(nums[i++], nums[j]);
        }
    }
    swap(nums[i], nums[r]);
    return i;
}

int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    int n = partition(nums, left, right);
    
    while (n != nums.size() - k) {
        if (n < nums.size() - k) {
            left = n + 1;
        } else {
            right = n - 1;
        }
        n = partition(nums, left, right);
    }
    return nums[n];
}

時間計算量：平均O(n)、最悪O(n²) 空間計算量：O(1)

2.5 インターバルのマージ（Merge Intervals）

問題説明：重複するインターバルをマージする。

解法の概要：

  • 左端でソート
  • インターバルを順に見ていき、マージできるか確認
  • マージ可能なら右端を更新、そうでなければ新しい区間を追加

実装コード：

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[0] < b[0];
         });

    vector<vector<int>> result;
    int left = intervals[0][0], right = intervals[0][1];
    
    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] <= right) {
            right = max(right, intervals[i][1]);
        } else {
            result.push_back({left, right});
            left = intervals[i][0];
            right = intervals[i][1];
        }
    }
    result.push_back({left, right});
    return result;
}

時間計算量：O(n log n) 空間計算量：O(log n)（ソートのスタック）

2.6 株価の売買（Best Time to Buy and Sell Stock）

問題説明：一度だけ売買して得られる最大利益を求める。

解法の概要：

  • 最低価格を記録
  • 各価格で利益を計算し、最大利益を更新

実装コード：

int maxProfit(vector<int>& prices) {
    int cost = prices[0];
    int profit = 0;
    
    for (int i = 1; i < prices.size(); i++) {
        cost = min(cost, prices[i]);
        profit = max(profit, prices[i] - cost);
    }
    return profit;
}

時間計算量：O(n) 空間計算量：O(1)

2.7 2つのソートされた配列のマージ（Merge Sorted Array）

問題説明：nums2をnums1にマージする（nums1には十分な領域がある）。

解法の概要：

  • 後ろから埋めていくことで、未処理の要素を上書きしない
  • 2つの配列の末尾から比較しながら挿入

実装コード：

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i1 = m - 1;
    int i2 = n - 1;
    
    for (int i = m + n - 1; i >= 0; i--) {
        if (i2 < 0 || (i1 >= 0 && nums1[i1] >= nums2[i2])) {
            nums1[i] = nums1[i1--];
        } else {
            nums1[i] = nums2[i2--];
        }
    }
}

時間計算量：O(m + n) 空間計算量：O(1)

3. 連結リスト操作

3.1 連結リストの反転（Reverse Linked List）

問題説明：単方向連結リストを反転する。

解法の概要：

  • prev、curr、nextの3つのポインタを使用
  • 各ノードのnextポインタを変更
  • 新しい頭を返す

実装コード：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

時間計算量：O(n) 空間計算量：O(1)

3.2 2つのソートされた連結リストのマージ（Merge Two Sorted Lists）

問題説明：2つの昇順連結リストを1つにマージする。

解法の概要：

  • 再帰的に処理
  • ノードの値を比較し、小さい方を先に選ぶ
  • 残りのリストを再帰呼び出し

実装コード：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr || list2 == nullptr) {
            return list1 == nullptr ? list2 : list1;
        }
        
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

時間計算量：O(m + n) 空間計算量：O(m + n)（再帰スタック）

4. 動的計画法

4.1 コイン交換（Coin Change）

問題説明：与えられた金額を最小のコイン数で支払う。

方法1：完全ナップサックDP

解法の概要：

  • dp[i]は金額iを支払うのに必要な最小コイン数
  • 状態遷移：dp[i] = min(dp[i], dp[i - coin] + 1)
  • 初期化：dp[0] = 0、他は無限大

実装コード：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

時間計算量：O(amount × n) 空間計算量：O(amount)

方法2：最適化バージョン

実装コード：

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 100000);
    dp[0] = 0;
    
    for (int i = 0; i < coins.size() && coins[i] <= amount; i++) {
        dp[coins[i]] = 1;
    }
    
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.size(); j++) {
            if (i - coins[j] > 0 && dp[i] > dp[i - coins[j]] + 1) {
                dp[i] = dp[i - coins[j]] + 1;
            }
        }
    }
    
    return dp[amount] == 100000 ? -1 : dp[amount];
}

5. 木の走査

5.1 層ごとのバイナリツリー走査（Binary Tree Level Order Traversal）

問題説明：バイナリツリーの各層ごとにノードの値を出力する。

解法の概要：

  • BFSにキューを使用
  • 各層のノード数を記録して分けて処理
  • 各層の値を結果配列に追加

実装コード：

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    queue<TreeNode*> q;
    
    if (root != nullptr) {
        q.push(root);
    }
    
    while (!q.empty()) {
        int size = q.size();
        vector<int> levelValues;
        
        for (int i = 0; i < size; i++) {
            TreeNode* current = q.front();
            q.pop();
            
            if (current->left) {
                q.push(current->left);
            }
            if (current->right) {
                q.push(current->right);
            }
            levelValues.push_back(current->val);
        }
        result.push_back(levelValues);
    }
    return result;
}

時間計算量：O(n) 空間計算量：O(n)

まとめ

この記事では以下のアルゴリズム問題と解法について紹介しました：

  • 文字列：スライディングウィンドウ、中心拡張
  • 配列：双方向ポインタ、ハッシュテーブル、クイックセレクト
  • 連結リスト：双方向ポインタ、再帰
  • 動的計画法：状態定義と遷移
  • 木：BFS層走査

これらの問題は面接で頻出なので、以下のように練習すると効果的です：

  1. 各アルゴリズムの核心を理解する
  2. 特殊ケースや境界条件を意識する
  3. 時間・空間複雑度を分析する
  4. 同じ種類の問題を繰り返し解くことで理解を深める

皆さんのアルゴリズム学習が顺利に進みますように！💪

タグ: アルゴリズム LeetCode C++ 文字列 配列

6月2日 16:49 投稿

ホットタグ

©2026 異端開発室