📖

LeetCode 01-two-sum - はじめてのLeetCode

2025/08/06に公開

LeetCode

tech

C++、pythonなどの第二言語習得のためコードを書きたい。データ構造とアルゴリズムを合わせて学習できるLeetCodeを利用した。

01-two-sum

https://leetcode.com/problems/two-sum

実装したコードが実行時間内に終わるように時間計算量と空間計算量を意識する必要がある。

時間計算量: アルゴリズムの実行時間を評価する指標
空間計算量: アルゴリズムが使用するメモリ量を評価する指標

最初の解法

二重ループですべての組み合わせを試す方法。
講義動画があり確認しながら実装したが、c++を書いたこともないので、そもそも書き方がわからなかった。

// Time: O(n^2)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++){
          for(int j = i + 1; j<nums.size(); j++){
            if (nums[j] == target - nums[i]){
              return{i,j};
          }
        }
    }
    return {};
  }
};

ハッシュマップを使った解法

補数(complement)を使ってnums配列から取得したい値を事前に計算して、1回のループで解を見つける

current + x = target
1 + x = 3
x = 3 - 1 => 2

のときに未知数はxなので、2の値がnums配列内にあるかどうかをチェックする。
なければ、hash配列に追加して次の数字を走査するため、そもそものループが一回少ない。

// Time: O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++){
            int cur = nums[i];
            int x = target - cur;
            if(hash.find(x) != hash.end()){
                return {hash[x], i};
            }
            hash[nums[i]] = i;
        }
        return {};
    }
};

時間計算量: O(n) - 配列を1回だけ走査
空間計算量: O(n) - ハッシュマップに最大n個の要素を格納

解いてみての感想

お題を選択して1問ずつ解けるのでコードを書く学習になった。コードの解法がないまま大海原に出されるatcoderなので、アルゴリズム学習という意味だとleetcodeから始めたほうが良さそう。
無学のc++でいきなり実装ではなく、他にruby,python,typescript版で実装して、処理の流れを先に掴んでおくほうがよかった。言語ごとの書き方の違いがわかって良い。

ruby

# NG. Time Limit ExceededになるためNG
# 最初の解法のブルートフォース法。
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
# def two_sum(nums, target)
#     nums.each_with_index do |num1, i|
#       nums.each_with_index do |num2, j|
#         next if i == j
#         return [i, j] if (num1 + num2) == target
#       end
#     end
# end

# OK.
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    hash = {}
    nums.each_with_index do |num, i|
      x = target - num
      return [i, hash[x]] if hash.key?(x)
      hash[num] = i
    end
end

python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        for index, num in enumerate(nums):
            x = target - num
            if x in hash:
                return [index, hash[x]] 
            hash[num] = index
        return []

typescript

function twoSum(nums: number[], target: number): number[] {
    const hash: Map<number, number> = new Map()
    // アロー関数のreturnは匿名関数の1イテレーションが終了するのみのため使えない。for関数を利用する
    for(let i = 0; i < nums.length; i++){
        const x = target - nums[i];
        if (hash.has(x)) {
            return [hash.get(x), i];
        }
        hash.set(nums[i], i);
    }
    return [];
};

c++

// Time: O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++){
            int x = target - nums[i];
            if(hash.find(x) != hash.end()){
                return {hash[x], i};
            }
            hash[nums[i]] = i;
        }
        return {};
    }
};

func twoSum(nums []int, target int) []int {
    h := make(map[int]int)

    for i, num := range nums{
        x := target - num
        if index, ok := h[x]; ok {
            return []int{index, i}
        }
        h[num] = i
    }
    return []int{}
}

01-two-sum

解いてみての感想

Discussion