「Dart」Leetcodeの第1問「Two Sum」
日本語版
問題
整数nums
の配列と整数target
が与えられたとき、2つの数値の足し算がtarget
になるようなインデックスを返します。
各入力にはちょうど1つの解があると仮定してもよいし,同じ要素を2度使ってもいけないです.
解答はどのような順番で返してもいいです。
例1
入力: 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つしか存在しない.
解決
この問題を線形時間で解くことは可能である。そのアイデアは、「ハッシュ」マップ
を利用して、既に訪問した要素のインデックス
を保存することである。 ハッシュマップ
の「キー」
は与えられた入力配列の番号である(各要素を訪問するたびにこれをハッシュマップに追加する)。ハッシュマップ
の"値" は、キー
で表される配列内の数値のインデックス
である。
このアルゴリズムは,与えられた入力配列に対して,以下のステップを実行する.
- 整数データ型を
キーと
値として受け付けるハッシュマップ
を作成する. - 与えられた配列の各要素を、最初の要素から順に反復処理する。
- 各反復において、必要数(必要数 = 目標和 - 現在の数)が
ハッシュマップ
に存在するかどうかを確認する。 - 存在すれば、{必要数インデックス, 現在数インデックス}を結果として返す。
- そうでなければ、現在の反復数を
キー
として、そのインデックス
を値としてハッシュマップ
に追加する。結果を見つけるまでこれを繰り返す。
コード
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:
- Create a
hash map
that accepts integer data types askeys
andvalues
. - Iterate over each element of the given array, starting with the first element.
- At each iteration, check whether the required number (required number = target sum - current number) exists in the hash map.
- If it exists, return {necessary number index, current number index} as a result.
- If not, add the current iteration number as
key
and itsindex
as value to thehash map
. Repeat this until the result is found.
Code
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