目录
题目概述(简单难度)
题目链接:
思路与代码
思路展现
这道题目使用哈希是最为简便的
代码示例
import java.util.*; import java.util.HashMap; public class Solution { /** * * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组 */ public int[] twoSum (int[] numbers, int target) { //map用于存储我们整形数组中的数字以及其在数组中对应的下标 HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 0 ; i < numbers.length ; i++) { if(map.containsKey(target - numbers[i])) { //注意这里的顺序为什么是这样 return new int[]{ map.get(target - numbers[i]) + 1 , i + 1}; }else { map.put(numbers[i] , i); } } return null; } }
时间复杂度:O(n)
一次遍历hashmap查找时间复杂度为O(1),for循环遍历n次,所以时间复杂度为O(N)
空间复杂度:O(n)
申请了n大小的map空间
注意事项
1:牛客中的很多集合都是需要自己导包的,例如这道题题目就需要我们自己导HashMap包
2:那么此时我们的map集合中到底存储的是什么呢?
map中存储的是我们数组中的每个值以及他们的下标
1
3:target - numbers[i]是一个非常巧妙的点,因为我们此时要在这个数组中找到等于target的两个值,并且我们想用一次遍历来完成,所以这样的设计就非常的巧妙了.
4:也是我比较犯迷糊的点,就是为什么这里返回的是new int[]{ map.get(target - numbers[i]) + 1 , i + 1}?
答:我们拿一个测试用例来做举例:
假设此时我们使用【3,2,4】 6这个测试用例来做举例
此时i走到3,发现6 - 3 = 3,map此时为空,根本不存在3这个元素,那么就将3这个元素加入到map当中,然后i走到了2,发现6 - 2 = 4,但是map此时只有3这个元素,并没有4这个元素,所以此时再将2加入到我们的map当中,最终i走到了4这个元素,6 - 4 = 2,发现map中有2这个元素,那么此时就要返回2和4所对应的下标了,因为题目中说了要按照下标升序的顺序返回,我们会发现4是最后才发现的,2是最先发现的,并且让返回的数组下标从1开始计数,所以说我们应该先返回map.get(target - numbers[i]) + 1 ,然后再返回i + 1