leetcode_01_两数之和

1. 题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

2.示例

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

3.思路分析

不能重复利用这个数组中同样的元素：意味着时间复杂度要为O(n)
通常，如果采用暴力法，则用两层循环，外层循环计算当前元素与 target 之间的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标，时间复杂度：O(n^2)。 内层循环查找差值很浪费时间，那么如何减少查询时间呢？利用 HashMap ！

4.代码实现

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

5.相关知识点

1.HashMap的基本操作
2.HashMap源码分析