一道使用算法解决的java题（关于hashmap的问题）

问题描述

问 题

leetcode的第一题，这种方法可以实现O(n)复杂度解

题目要求是给一个int[],例如 nums = [2, 7, 11, 15]，给一个target = 9。
若存在两个数的和为target值，例如 nums[0] + nums[1] = 2 + 7 = 9
return [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)如果先初始化，花费算法时间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)直到遍历到７, target - 7 = 9 - 7 = 2
　4)判断2在map,返回正确结果
　注意，要遍历到第二个正确数.

这篇关于一道使用算法解决的java题（关于hashmap的问题）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！