Zenn
🗂

「Dart」Leetcodeの第1問「Two Sum」

2022/10/31に公開
Dart
tech

日本語版

問題

整数numsの配列と整数targetが与えられたとき、2つの数値の足し算がtargetになるようなインデックスを返します。

各入力にはちょうど1つの解があると仮定してもよいし，同じ要素を2度使ってもいけないです．

解答はどのような順番で返してもいいです。

例１

入力: nums = [2,7,11,15], target = 9
出力: [0,1]
説明: nums[0] + nums[1] == 9なので [0, 1]のインデックスを返します.

例2

入力: nums = [3,2,4], target = 6
出力: [1,2]

例3

入力: nums = [3,3], target = 6
出力: [0,1]

制約条件

  • 2 <= nums.length <= 10^{4}
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 有効な答えは1つしか存在しない.

解決

この問題を線形時間で解くことは可能である。そのアイデアは、「ハッシュ」マップを利用して、既に訪問した要素のインデックスを保存することである。 ハッシュマップの「キー」は与えられた入力配列の番号である（各要素を訪問するたびにこれをハッシュマップに追加する）。ハッシュマップの"値" は、キーで表される配列内の数値のインデックスである。

このアルゴリズムは，与えられた入力配列に対して，以下のステップを実行する．

  1. 整数データ型をキーと値として受け付けるハッシュマップを作成する．
  2. 与えられた配列の各要素を、最初の要素から順に反復処理する。
  3. 各反復において、必要数（必要数 = 目標和 - 現在の数）がハッシュマップに存在するかどうかを確認する。
  4. 存在すれば、{必要数インデックス, 現在数インデックス}を結果として返す。
  5. そうでなければ、現在の反復数をキーとして、そのインデックスを値としてハッシュマップに追加する。結果を見つけるまでこれを繰り返す。

コード

two_sums.dart
class Solution {
  List<int> twoSum(List<int> nums, int target) {
      Map indexMap={};
      for(var i=0;i<nums.length;i++){
          var requiredNum = (target - nums[i]);
          if(indexMap.containsKey(requiredNum)){
              return [indexMap[requiredNum],i];
            }

            indexMap[nums[i]]= i;
        }
        return [];
    }
      }

参考: leetcode

English ver.

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints

  • 2 <= nums.length <= 10^{4}
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Solution

It is possible to solve this problem in linear time. The idea is to use a 'hash' map to store an index of the elements already visited. The "key" of the hash map is the number of the given input array (each time an element is visited, this is added to the hash map). The hashmap "value" is the index of the number in the array represented by the hashmap key.

The algorithm performs the following steps for a given input array:

  1. Create a hash map that accepts integer data types as keys and values.
  2. Iterate over each element of the given array, starting with the first element.
  3. At each iteration, check whether the required number (required number = target sum - current number) exists in the hash map.
  4. If it exists, return {necessary number index, current number index} as a result.
  5. If not, add the current iteration number as key and its index as value to the hash map. Repeat this until the result is found.

Code

two_sums.dart
class Solution {
  List<int> twoSum(List<int> nums, int target) {
      Map indexMap={};
      for(var i=0;i<nums.length;i++){
          var requiredNum = (target - nums[i]);
          if(indexMap.containsKey(requiredNum)){
              return [indexMap[requiredNum],i];
            }

            indexMap[nums[i]]= i;
        }
        return [];
    }
      }

Discussion