力扣系列(一)：两数之和

• 描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。(你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。)
• 示例

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

• 思路：再循环遍历数组的时候，检查目标值(target-nums[i])是否存在，如果存在，说明数据中存在两个数的和是目标值，返回对应下标(new int[]{map.get(num),i})；如果不存在，把值及对应下标保存起来继续向下遍历。

public class TwoSum_01 {
    public static void main(String[] args) {
        TwoSum_01 twoSum_01 = new TwoSum_01();
        int[] nums = {1,2,4,8,14};
        int target = 9;
        int[] ints = twoSum_01.twoSum(nums, target);
        System.out.println(ints[0]+" "+ints[1]);
    }
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<nums.length;i++){
           int num = target-nums[i];
           if(map.containsKey(num)){
               return new int[]{map.get(num),i};
           }
           map.put(nums[i],i);
        }
        throw new RuntimeException("not find value");
    }
}

• 时间复杂度：O(N)
  我们仅进行一次遍历数组(map中get操作可以看成是O(1)时间复杂度)
• 空间复杂度：O（N）
  需要一个map来存储中间变量值，最多会存储n-1个键值对