Two Sum

1package pkg5leetcode;2 3/*4 * LeetCode 1: Two Sum  (Easy)5 * ---------------------------6 * Given an array and a target, return indices of the two numbers that add up to target.7 *8 * APPROACH: one-pass hash map. For each x, check if (target - x) was seen.9 * COMPLEXITY: Time O(n), Space O(n).  Brute force is O(n^2).10 */11import java.util.*;12 13public class leetcode1TwoSum {14 15    static int[] twoSum(int[] nums, int target) {16        Map<Integer, Integer> seen = new HashMap<>();   // value -> index17        for (int i = 0; i < nums.length; i++) {18            int need = target - nums[i];19            if (seen.containsKey(need)) return new int[]{seen.get(need), i};20            seen.put(nums[i], i);21        }22        return new int[]{-1, -1};23    }24 25    public static void main(String[] args) {26        check(Arrays.equals(twoSum(new int[]{2, 7, 11, 15}, 9), new int[]{0, 1}), "case1");27        check(Arrays.equals(twoSum(new int[]{3, 2, 4}, 6), new int[]{1, 2}), "case2");28        check(Arrays.equals(twoSum(new int[]{3, 3}, 6), new int[]{0, 1}), "case3");29        System.out.println("leetcode1TwoSum: all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}