今天做这道!!
7.两数之和

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

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

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

所以返回 [0, 1]

https://leetcode-cn.com/problems/two-sum/

  u1s1 就是让你知道hash表查询时间复杂度为O(1)
O(1)。

思路:
  题目要求得到在数组中取出两个数之和等于target的下标,所以首先考虑如何取出和等于target的两个数,总所周知哈希表的查询时间复杂度是

  

过程:
首先需要一个for循环遍历整个数组,并将数组中的数据根据key(number):value(index)的形式存储在hashmap中(hashmap是通过hash值经过与运算得到数据存储下标的,重复的概率很小,若重复则在数组位置通过头插法插入链表,当然是jdk1.7的时候),在插入的同时,进行判断 target-n[i]是否在map当中,若存在则返回该值的value 和 i,若不存在则继续循环,直到最后循环结束。
  

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = target - nums[i];
            if (map.containsKey(num)) {
                int index = map.get(num);
                return new int[] {index,i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}