Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

Two Sum用hashmap存需要找到的另一个数，如果找到就记录坐标。

public int[] twoSum(int[] numbers, int target) {
        int[] results = {0,0};
        if (numbers==null||numbers.length==0) {
            return results;
        }

        Map<Integer, Integer> numberMap = new HashMap<Integer, Integer>();

        //the idea is to put the other number in the map, if the other number is found, return the pair
        for (int i=0; i<numbers.length; i++) {
            if (numberMap.containsKey(numbers[i])) {
                results[0] = numberMap.get(numbers[i]) + 1;
                results[1] = i+1;
                break;
            } else {
                //store the other number and current index
                numberMap.put(target-numbers[i], i);
            }
        }
        return results;
    }

Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

如果已经排好序，就可以移动start与end指针，O(n)解法。

public int[] twoSum(int[] numbers, int target) {
        int[] results = {0,0};
        if (numbers==null||numbers.length==0) {
            return results;
        }


        //the idea is to put the other number in the map, if the other number is found, return the pair
        int i=0;
        int j=numbers.length-1;
        while (i<j) {
            int sum = numbers[i]+numbers[j];
            if (sum==target) {
                results[0] = numbers[i];
                results[1] = numbers[j];
                break;
            } else if (sum<target) {
                i++;
            } else {
                j--;
            }
        }       
        return results;
    }

Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value.

For example, add(1); add(3); add(5); find(4) -> true find(7) -> false

因为允许重复元素，所以用map来存当前元素出现的次数，add是O(1)，find是O(n)，当在map中发现另一半的时候，如果另一半是key本身则判断key是不是出现过大于1次，如果不是本身说明已经找到。

public class TwoSumIII {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    public void add(int number) {
        if (map.get(number)==null) {
            map.put(number, 1);
        } else {
            map.put(number, map.get(number)+1);
        }
    }

    public boolean find(int value) {
        for (Entry<Integer, Integer> entry : map.entrySet()) {
            int key = entry.getKey();
            int times = entry.getValue();
            int rest = value - key;

            if (map.containsKey(rest)) {
                if (rest==key) {
                    return times>1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }
}