1. 两数之和

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题方法

思路一 ： 暴力法

暴力法非常简单， 从首元素开始依次扫描，记录下此元素与target的差值，往后遍历，之后元素与target一致时，返回元素下标。

时间复杂度：O（N ^ 2）,空间复杂度(O(1))

思路二 ：两遍哈希表

二次迭代，第一遍迭代先把index 和 与target的差值存入map， 第二次迭代检查每个元素对应的差值，是否存在map中。有则返回下标。

时间复杂度：O（N ）,空间复杂度(O(N))

思路三 ：一遍哈希表

一次迭代，迭代时判断map的key中是否存在nums[i], 如果存在，则返回i 和 map.get[nums[i]], 不存在则把map中存放(target - nums[i], i).

时间复杂度：O（N ）,空间复杂度(O(N))

代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

 public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
          // 如果map的key中包含，当前元素
            if (map.containsKey(nums[i])){
              // 则map的value ，i就是结果数组
                int [] res = {map.get(nums[i]),i};
                return res;
            }
          // map的key中不包含当前元素，则把target和当前元素的差值和i存入map
            map.put(target - nums[i],i);
        }
        return new int[0];
    }