一道使用算法解决的java题(关于hashmap的问题)
问题描述
leetcode的第一题,这种方法可以实现O(n)复杂度解
题目要求是给一个int[],例如 nums = [2, 7, 11, 15],给一个target = 9。若存在两个数的和为target值,例如 nums[0] + nums[1] = 2 + 7 = 9return [0, 1].
使用如下解法的时候,有一点疑惑,就是new了一个hashmap,但是并没有给他赋值,这种情况下是如何实现题目要求的呢?
public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) {if (map.containsKey(target - numbers[i])) { result[1] = i + 1; result[0] = map.get(target - numbers[i]); return result;}map.put(numbers[i], i + 1); } return result;}
问题解答
回答1:for循环里面的map.put()不是赋值吗???
回答2:题目是要求得两个数的和为目标值为给定值,那么一定要遍历至少两个数.(1)如果先初始化,花费算法时间O(n);然后再遍历查找到第一正确的值时,需要算法时间O(k), 0<k<n.总时间是O(n+k), 要判断是不是自己,如(10 = 5 + 5).这种情况实现是:
1)先初始化map, 2)遍历第一个数2, target - 2 = 9 - 2 = 7 3)判断7也在map中,返回正确结果. 注意:要遍历到第一个正确数
(2)如果不县初始化,那么一定会遍历到第二个正确的数,才停止,算法时间为O(k)(1<k<=n).不用判断自己. 这种情况实现是:
1)遍历第一个数2, target - 2 = 9 - 2 = 7 2)判断7是否在map,发现不在,把2加入map,继续遍历 3)直到遍历到7, target - 7 = 9 - 7 = 2 4)判断2在map,返回正确结果 注意,要遍历到第二个正确数.回答3:
没有 Key 的情况下,HashMap.containsKey(Key) 返回的是 false 不包括 Key。
public boolean containsKey(Object key) {return getNode(hash(key), key) != null; }
不会出现你所想的空指针错误。
相关文章:
1. docker gitlab 如何git clone?2. android - 目前有哪些用Vue.js开发移动App的方案?3. font-family - 我引入CSS3自定义字体没有效果?4. 在windows下安装docker Toolbox 启动Docker Quickstart Terminal 失败!5. docker镜像push报错6. PHP中的$this代表当前的类还是方法?7. nignx - docker内nginx 80端口被占用8. angular.js - 求一款angular插件9. docker images显示的镜像过多,狗眼被亮瞎了,怎么办?10. PHP类中的$this