LeetCode #1 TwoSum

問題概要

入力値：nums(intの配列), target(int)
出力値：answer(intの配列)
numsの中から和がtargetになるnumsの2つのインデックス値の配列を求める
問題のリンク

入力例

nums: [1,2,3]
target: 5
answer: [1,2]

解答例1

Brute force
計算量：n^2

Python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

Runtime: 2156ms
Beats: 29.04%

解答例2

一度取得したデータを辞書に保存していくことでforを1つにする
計算量：n

Python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_to_index = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in num_to_index:
                return [num_to_index[diff], i]
            num_to_index[num] = i
        return []

Runtime: 42ms
Beats: 62.39%

C++

#include <unordered_map>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;

        for (int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (mp.find(diff) == mp.end())
                mp[nums[i]] = i;
            else
                return {mp[diff], i};
        }
        return {-1, -1};
    }
};

Runtime: 3ms
Beats: 98.46%