今天做这道!!
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"); } }