LeetCode #1 Two Sum プログラミング練習
こんにちは!初はてなブログです。
日本人にはあまり馴染みのないかもしれないLeetCodeですが、実はアメリカや中国では情報系の学生なら誰もが一日一問解いていると言われる超有名練習問題です。
(実はグーグルやフェイスブック等アメリカ有名企業の面接問題は80%LeetCodeから出ます)
英語しか対応していないと言うこともあり、今日からLeetCodeの問題の翻訳と自分の回答を書いていきたいと思います。
他の回答方法を持っている方、改善方法等があればコメントお願いします。
1.Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
難易度: easy
入力: 整数のArray、ターゲットの整数
目的: 入力Arrayの中から足したらターゲット整数に値する二つの整数のインデックスを探せ
出力: 目的インデックスのArray
注意: 答えは必ず一つ存在する。同じ要素は一度しか使えない
グーグル過去問でよく出ると言われる基礎問題です。
自分の回答を貼ります。
class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; HashMap<Integer, Integer> index = new HashMap<>(); for (int i=0; i<nums.length; i++) { int temp = target - nums[i]; if (index.containsKey(temp)) { res[0] = index.get(temp); res[1] = i; break; } else index.put(nums[i], i); } return res; } }
まずHashMapを用意し、
target - nums[i]でi番目の要素とtargetとの差がMapの中にあるかどうか判断します。
なければi番目の要素とindexをmapに格納。
あればmapからindexを取り出し出力します。
では今日はここまで。