LeetCode题库-1

题目：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用

示例:

给定nums = {2,7,11,15} ,target=9

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

所以返回[0,1]

解题思路：

根据给出的实例可以知道，找到数组中两个数的和为目标值在数组的位置，然后将这两个位置放进一个新数组并返回。

根据上面的解题思路，很容易想到一个比较暴力的解法，使用双重循环遍历整个数组得到结果

代码：

class Solution {
   public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length < 2)
            return res;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        return res;
    }  
}

上面这种解法是最简单也最无脑的一种方法了，将LeetCode里面给的实例全部运行完需要比较长的时间。

另外一种方法主要是使用HashMap来实现，代码如下：

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

通过遍历数组，将数组里面的值作为Key键，对应的数组值的索引作为Value值传入到HashMap中存储，每循环一次就判断目标值target和当前数组索引所对应的值的差，是否在在HashMap的Key值中，如果在就说明这两个数相加能得到目标值，此时就可以得到当前遍历的数组的索引和HashMap的Key所对应的Value值就是需要得到的位置。