LeetCode: Two Sum
はじめに
LeetCodeを始めてみた。 その1問目がこれ。
問題
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.
僕の解答
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int[] { i, j }; } } } return new int[] { 0, 0 }; } }
とりあえず何も考えずに解いてみるかという感じで何も考えずにO(n2)で回しました。
でもこの解答、周りの人のに比べるとすごい遅いんですよね(O(n2)だから当たり前か。)。
それで他の人(の多くは)どう解答しているのか見てみることにします。 (LeetCodeは他の人の解答が見られるのがいいですね。)
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> ht = new HashMap<Integer, Integer>(); int[] twoSum = new int[2]; if (nums == null || nums.length < 2) return twoSum; for (int i=0; i<nums.length; i++) { if (ht.containsKey(nums[i])) { twoSum[0] = ht.get(nums[i]); twoSum[1] = i; return twoSum; } else { ht.put(target-nums[i], i); } } return twoSum; } }
なるほど、Mapを使ってO(n)にしてるんですね。これは結構簡単だけど使えそうなテクニックですね。
おわりに
LeetCodeがんばります。