001-两数之和

一、题目（001—简单）

二、分析

   首先想到的应该是两次for循环，外层for循环先选定一个数组元素，根据target和数组元素之间值的关系，内层for循环遍历，并获取到这两个元素的下标值，返回。这个方法的时间复杂度是O(n^2).
   我们根据题意，数组两个目标元素不可以重复（注意，是不同下标，不是不同值），就可以用到map这种数据结构。根据map的特点，key—value键值对中，key不可重复，value可以重复。因此我们可以考虑创建一张哈希表（hashmap）来存key。

三、题解

1、暴力解法

class Solution {

    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 (target == nums[i]+nums[j]){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{};
    }

}

2、优化解法

class Solution {

    public int[] twoSum(int[] nums, int target) {
        //建立一张哈希表
        Map<Integer, Integer> map = new HashMap<>();
        //由左向右遍历数组
        for(int i = 0; i< nums.length; i++) {
            //判断是否存在数组元素等于target和当前下标元素的差值
            if(map.containsKey(target - nums[i])) {
                //如果存在，返回该元素和下标
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

}

参考的图解步骤如下：