/**
 * Problem: #1 Two Sum
 *
 * Idea: iterate through each number in the nums, compare the difference between target
 * and the current number, find if the difference exists as an item in the rest of the
 * array nums.
 *
 * Solutions:
 *  twoSum: Brute Force O(n^2)
 *  twoSumHash2: Use hash table to trade space for time O(n)
 *  twoSumHash: One loop, examining and add new.
 */

import java.util.HashMap;
import java.util.Hashtable;

public class TwoSum {
    private static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j< nums.length; j++) {
                if (target - nums[i] == nums[j]) {
                    return new int[] {i, j};
                }
            }
        }
        throw new IllegalArgumentException("Now solution found.");
    }

    private static int[] twoSumHash2(int[] nums, int target) {
        Hashtable<Integer, Integer> hash = new Hashtable<>();
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (hash.containsKey(diff) && hash.get(diff) != i) {
                return new int[] {i, hash.get(diff)};
            }
        }
        throw new IllegalArgumentException("No solution found");
    }

    private static int[] twoSumHash(int[] nums, int target) {
        HashMap<Integer, Integer> hash = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (hash.containsKey(complement) && hash.get(complement) != i) {
                return new int[] {hash.get(complement), i};
            }
            hash.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solutions found");
    }

    public static void main(String[] args) {
        int[] nums = new int[] {2, 7, 11, 15};
        int target = 9;

        int[] result0 = twoSum(nums, target);
        int[] result1 = twoSumHash2(nums, target);
        int[] result2 = twoSumHash(nums, target);

        System.out.println("[" + result0[0] + ", " + result0[1] + "]");
        System.out.println("[" + result1[0] + ", " + result1[1] + "]");
        System.out.println("[" + result2[0] + ", " + result2[1] + "]");
  }
}

@@ -376,16 +376,38 @@
 w.%0A */%0A%0A
+import java.util.Map;%0A
 import j
@@ -1849,24 +1849,454 @@
 d%22);%0A    %7D%0A%0A
+    private static int%5B%5D twoSumHashMap(int%5B%5D nums, int target) %7B%0A        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            int complement = target - nums%5Bi%5D;%0A%0A            if (map.containsKey(complement)) %7B%0A                return new int%5B%5D %7Bmap.get(complement), i%7D;%0A            %7D else %7B%0A                map.put(nums%5Bi%5D, i);%0A            %7D%0A       %7D%0A%0A       return null;%0A    %7D%0A%0A
     public s
@@ -2324,24 +2324,24 @@
 g%5B%5D args) %7B%0A
-
         int%5B
@@ -2546,16 +2546,69 @@
 target);
+%0A        int%5B%5D result3 = twoSumHashMap(nums, target);
 %0A%0A      
@@ -2737,32 +2737,32 @@
 ult1%5B1%5D + %22%5D%22);%0A
-
         System.o
@@ -2817,14 +2817,86 @@
 + %22%5D%22);%0A
+        System.out.println(%22%5B%22 + result3%5B0%5D + %22, %22 + result3%5B1%5D + %22%5D%22);%0A
   %7D%0A%7D%0A

Update TwoSum