# LeetCode Easy 1. Two Sum

tags: leetcode

LeetCode

いきなりですが外資系のIT企業でバリバリコードが書きたくなったのでLeetCodeの問題を解いていこうと思います

LeetCodeとは企業がCoding Interviewの問題を使ったオンラインジャッジサイトです

グレーな感じがしますが,使えるものはなんでも使うがモットーなので使います

ところで他のオンラインジャッジサイトと異なり,手元の環境でやりにくい(VSCodeでLeetCodeがやれる拡張機能があったのですが現在使えません)です

しかし,サイト内でコーディングがしやすく,実際コーディング試験ではパソコンが使えない場合も多いらしい(ホワイトボードを使う)のでこれでいいのかなと

LeetCodeでは出入力を考える必要はなく,与えられたクラスの中にコードを書くようになっています.そのため競技プログラミングの初心者でもやりやすいはずです

方針

ということでLeetCodeの問題の日本語での要約,解法(に加えてPythonとC++でのコード)を適当に書いて載せます

解法に関しては問題ごとにSolutionやDiscussというコーナーがあり,ここに公式,非公式での解法があります

わからない問題は他人の解答をしれっと丸パクリしていることもあると思いますが,別に著作権も何もないと思うのでどこが元かは言及しません

あくまでただのメモなので解法が間違っていたらコメントなどで優しく教えて下さい

問題

今回は初回ということで最も有名な(悪名高い?)Two Sumという問題を扱おうと思います

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

与えられた整数のarrayからある特定の値に足し合わせられるような2つの要素の添字を返せ

ただし解はただ1つ存在すると仮定して良く,同じ要素を2回使っては行けない

解法1

一番単純な解法は総当りするものですね

• 与えられたarrayから1つの要素を選び,それ以外の要素を1つ選びます
• 2つの要素の和がtargetと同じとき,2つの要素の添字を返します
• arrayの長さを$n$とすると
  • 空間計算量は$O(1)$
  • 時間計算量は$O(n^{2})$

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l = len(nums)
        for i in range(l):
            for j in range(i+1, l):
                if nums[i] + nums[j] == target:
                    return [i, j]

C++

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

解法2

当然上の解法では時間計算量が大きいので改善します

• nums[i] + nums[j] == targetとなるような要素を見つけたいです
  • 逆にtarget - nums[i] = nums[i]となるようなnums[i]を探せば良いのでは?という風に考えることができるはずです
• この解法はハッシュを用いた連想配列(以降map)を使います
  • target - nums[i]をkey, 添字をvalueとするmapを定義します
  • nums[i]がkeyにあればnums[i] == target - nums[j]となるようなtarget - nums[j]がmapのkeyに入っているということです.そしてこのvalueはj
    • そのため,nums[i]を使ってnum[j]の添字jを取得し,jとiを出力すれば良いです
  • もしnums[i]がkeyなれば
    • だからtarget - nums[j]をkey,添字jをvalueとしてmapに新しい要素を挿入します
  • arrayの長さが$n$のとき
  • 空間計算量は$O(n)$
  • 時間計算量は$O(n)$で済みます

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l = len(nums)
        dic = {}
        for i in range(l):
            cmp = target - nums[i]
            if nums[i] in dic:
                return [dic[nums[i]], i]
            else:
                dic[cmp] = i

C++

• C++にはmapというSTLがありますが,実装が平行二分木でされています
  • 検索の時間計算量が$O(log(n))$です
• これでは遅いので,ハッシュテーブルを使うunordered_mapを使う
  • 検索の時間計算量が$O(1)$でありより高速です

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> mp;
        auto n = nums.size();
        for (int i = 0; i < n; i++) {
            int cmp = target - nums[i];
            if (mp.find(nums[i]) != mp.end()) {
                return {mp[nums[i]], i};
            } else {
                mp[cmp] = i;
            }
        }
        return {-1, -1};
    }
};

次回から

次回はExploreという問題が体系的にまとまっているところの問題を解説していきます