自分の解答
int配列の中から2つを取り出し、足した値がTargetと同じになる組み合わせを探す問題。
2重ループ。Accept
public int[] twoSum(int[] nums, int target) { int[] answer = new int[2]; for(int i = 0; i < nums.length; i++) { for(int j = i + 1; j < nums.length; j++) { if(nums[i] + nums[j] == target) { answer[0] = i; answer[1] = j; return answer; } } } return null; }
自分の解答2
HashMap使おうとしたが駄目だったパターン。
求める答えを先に出しておく。
// HashMapバージョン /** 結果はWrong。 * Target = 6; nums = {3, 1, 3}の場合 * HashMapに重複するキーを登録してしまうため * * あとTarget = 4 nums{2, 1, 3}もだめ。 * 答え[0, 0] を返す可能性があるため。本来は[1, 2] * **/ public int[] twoSum2(int[] nums, int target) { int[] answerArray = new int[2]; Map<Integer, Integer> map = new HashMap<>(); // 配列をHashMapに格納 for(int i = 0; i < nums.length; i++) { map.put(nums[i], i); //←同じKeyだと上書きされてしまう } // 1重ループで答え探し for (Map.Entry<Integer, Integer> entry : map.entrySet()) { int answer = target - entry.getKey(); answerArray[0] = map.get(answer); answerArray[1] = entry.getValue(); return answerArray; } return null; }
模範解答
重複を避けるテクニックがニクいね!
// 模範解答 public int[] twoSum3(int[] nums, int target) { HashMap<Integer, Integer> prevMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; int diff = target - num; if (prevMap.containsKey(diff)) { return new int[] { prevMap.get(diff), i }; } prevMap.put(num, i);// ←あとから追加するので重複を避けられる } return new int[] {}; }
・引用元
学んだこと
以前に何かで読んだ気がするのだけど、求める答えがわかっている場合は先に出力しておくと良いっぽい。
今回の場合は answer = Target - num[i] のところ。