leetcode第一题Two Sum

首先我们先看英文通过大致阅读，再根据下方中文对比。以防止以后面试会遇到一些英文题目。强烈建议不要用编译器解答，直接用leetcode上的，因为平时会有代码提示，会忽略很多细节上的东西，当自己写的时候就会出现，这也是我最近开始弄这个的时候发现的。

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].

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

下面对本题目进行分析：
最简单的方法就是遍历两次这个数组，用target-nums[i]来作为两重嵌套的终结目标，如下代码所示

/**
 * Two Sum
 * 两数之和
*/

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

但是我们知道这样由于两重嵌套，算法的复杂度是O(N^2)，因此我们一般不采用这种。
我们只想用线性的时间复杂度来解决问题，那么就是说只能遍历一个数字，那么另一个数字呢，我们可以事先将其存储起来，使用HashMap，来建立数字和其坐标位置之间的映射，我们都知道HashMap是常数级的查找效率，这样，我们在遍历数组的时候，用target减去遍历到的数字，就是另一个需要的数字了，直接在HashMap中查找其是否存在即可，注意要判断查找到的数字不是第一个数字，比如target是4，遍历到了一个2，那么另外一个2不能是之前那个2，整个实现步骤为：先遍历一遍数组，建立HashMap映射，然后再遍历一遍，开始查找，找到则记录index。代码如下：

第一种：

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; ++i) {
            m.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; ++i) {
            int t = target - nums[i];
            if (m.containsKey(t) && m.get(t) != i) {
                res[0] = i;
                res[1] = m.get(t);
                break;
            }
        }
        return res;
    }
}

第二种：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> m=new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            if(m.containsKey(target-nums[i])){
                return new int[]{i,m.get(target-nums[i])};
            }
              m.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
} 

我们分析一下上面两种方法，第一种看似没有什么问题，先将所有的数存入HashMap，再通过一次遍历查询到t，判断再HashMap中是否包含t，而且不是以前的key。但是我们是不是忽略了一点，题目中没有说所给的数组没有重复，如果有重复那么存入的时候会将之前相同的key，所对应的value覆盖掉，因此这也是这道题的小bug，虽然能通过但是细心的思考他题目上是说的不明确的。
第二种方法就是在第一种方法上的改进，解决了上述问题，边比较值同时，边存入数据，这样每次我们在存入前已经进行了比较，也就是之前的之已经没用了，我们下次比较的都是新的值，即时替换了也无所谓，因为被替换掉的数已经通过了测试，其不是我们需要的值。