package com.freetymekiyan.algorithms.level.medium;

import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 * <p>
 * You may assume that each input would have exactly one solution.
 * <p>
 * Example:
 * Given nums = [2, 7, 11, 15], target = 9,
 * <p>
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 * <p>
 * UPDATE (2016/2/13):
 * The return format had been changed to zero-based indices. Please read the above updated description carefully.
 * <p>
 * Company Tags: LinkedIn, Uber, Airbnb, Facebook, Amazon, Microsoft, Apple, Yahoo, Dropbox, Bloomberg, Yelp, Adobe
 * Tags: Array, Hash Table
 * Similar Problems: (M) 3Sum, (M) 4Sum, (M) Two Sum II - Input array is sorted, (E) Two Sum III - Data structure
 * design
 */
public class TwoSum {

    private TwoSum t;

    /**
     * Hash Table. O(n) time, O(n) space.
     * This method is an optimization from the brute-force method,
     * which we search for the other target with a second loop.
     * We put number as key , index as value.
     * Search new target in map, and make sure it is not the same number.
     * So check the indices of current position and what we get from the map.
     * If there is no match, just return null.
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int newTarget = target - nums[i];
            if (map.containsKey(newTarget) && i != map.get(newTarget)) {
                return new int[]{i, map.get(newTarget)};
            }
        }
        return null;
    }

    @Before
    public void setUp() {
        t = new TwoSum();
    }

    @Test
    public void testExamples() {
        int[] numbers = {3, 2, 4}; // 6 = 3 + 3
        int target = 6;
        int[] res = t.twoSum(numbers, target);
        Assert.assertArrayEquals(new int[]{1, 2}, res);

        numbers = new int[]{2, 7, 11, 15};
        target = 9;
        res = t.twoSum(numbers, target);
        Assert.assertArrayEquals(new int[]{0, 1}, res);
    }

    @After
    public void tearDown() {
        t = null;
    }
}
@@ -1878,24 +1878,714 @@
 ull;%0A    %7D%0A%0A
+    /**%0A     * Hash Table. One loop.%0A     * Just put numbers into the map as looping through.%0A     * So we can search numbers already looped in O(1).%0A     * Note that if we find an answer, we current index will be larger than the index in map.%0A     * So put it behind.%0A     */%0A    public int%5B%5D twoSumB(int%5B%5D nums, int target) %7B%0A        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            int newTarget = target - nums%5Bi%5D;%0A            if (map.containsKey(newTarget) && i != map.get(newTarget)) %7B%0A                return new int%5B%5D%7Bmap.get(newTarget), i%7D;%0A            %7D%0A            map.put(nums%5Bi%5D, i);%0A        %7D%0A        return null;%0A    %7D%0A%0A
     @Before%0A

update two sum with one loop solution