1、Two Sum

题设

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

要点

• Hash表，将双重循环的O(n^2)降到O(n)
• 排序+首尾指针，不断移动

该题其实就是一个很简单的搜索问题，但是如果暴力搜索的话，需要遍历两次数组，时间复杂度是O(n^2)，空间O(1)。
可以采用hash表，把数组按照值-索引的映射存入hash表，这样就只需要对hash表进行一次遍历，时间复杂度降为O(1)，空间复杂度O(n)。
或者对数组进行一次从小到大排序，然后维护两个首尾指针，将和的大小与target进行比较，不断移动指针。

        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++) // 值-索引 存入hash表
            map.put(nums[i], i);
        
        int[] result = new int[2];
        for(int i = 0;i < nums.length;i++) // 之后只需要在hash表中进行搜索，时间只需要O(n)
        {
            int temp = target - nums[i];
            if(map.containsKey(temp))
            {
                if(map.get(temp) == i)
                    continue;
                result[0] = i;
                result[1] = map.get(temp);
                break;
            }
        }