https://oj.leetcode.com/problems/two-sum/

http://fisherlei.blogspot.com/2013/03/leetcode-two-sum-solution.html

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        
        // Solution A
        // return twoSum_SortAndTwoPointer(numbers, target);
        
        // Solution B
        return twoSum_Map(numbers, target);
    }
    
    /////////////////////////////
    // Solution 2: Map
    // 
    // Map[target - value, index]
    public int[] twoSum_Map(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0 ; i < numbers.length ; i ++)
        {
            Integer j = map.get(numbers[i]);
            if (j != null)
            {
                i++;
                j++;
                return new int[] {Math.min(i, j), Math.max(i, j)};
            }
            else
            {
                map.put(target - numbers[i], i);
            }
        }
        return null;
    }
    
    /////////////////////////////
    // Solution 1: Sort and iteration with 2 index
    //
    // 数组排序
    // 使用两个index分别从头和尾遍历
    // 此方法可扩展至three sum， four sum
    
    public int[] twoSum_SortAndTwoPointer(int[] numbers, int target) {
        
        int len = numbers.length;
        List<IndexValue> nums = new ArrayList<>(len);
        for (int i = 0 ; i < len ; i ++)
        {
            nums.add(new IndexValue(i, numbers[i]));
        }
        
        // Sort
        Collections.sort(nums, new Comparator<IndexValue>()
        {
            public int compare(IndexValue a, IndexValue b)
            {
                return Integer.compare(a.value, b.value);
            }
        });
        
        int start = 0;
        int end = len - 1;
        while (start < end)
        {
            int sum = nums.get(start).value + nums.get(end).value;
            if (sum == target)
            {
                int a = nums.get(start).index + 1;
                int b = nums.get(end).index + 1;
                return new int[] {Math.min(a, b), Math.max(a, b)};
            }
            else if (sum < target)
            {
                start++;
            }
            else
            {
                end--;
            }
        }
        return null;
    }
    
    private static class IndexValue
    {
        int index;
        int value;
        IndexValue(int index, int value)
        {
            this.index = index;
            this.value = value;
        }
    }
}

[LeetCode]1 Two Sum