A Java problem solved using an algorithm (problem about hashmap)
阿神
阿神 2017-05-27 17:41:09
0
3
627

The first question of leetcode, this method can achieve O(n) complexity solution

The question requires an int[], such as nums = [2, 7, 11, 15], and a target = 9.
If there are two numbers whose sum is the target value, for example nums[0] nums[1] = 2 7 = 9
return [0, 1].

When using the following solution, I have a little doubt, that is, a new hashmap is created, but no value is assigned to it. In this case, how do you achieve the question requirements?

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;
}
阿神
阿神

闭关修行中......

reply all(3)
phpcn_u1582

Isn’t map.put() in the for loop an assignment? ? ?

曾经蜡笔没有小新

The question requires that the sum of two numbers be the target value and a given value, then you must traverse at least two numbers.
(1) If you initialize first, it will take algorithm time O(n); then traverse to find the first When the value is correct, the algorithm time is O(k), 0<k<n. The total time is O(n+k), to determine whether it is yourself, such as (10 = 5 + 5).
 The realization of this situation is:

  1) Initialize the map first,
  2) Traverse the first number 2, target - 2 = 9 - 2 = 7
  3) Judge that 7 is also in the map and return the correct result.
Note: Traverse to the first correct number

 
(2) If it is not initialized, it will traverse to the second correct number before stopping. The algorithm time is O(k)(1<k<=n). There is no need to judge yourself.
The realization of this situation is:

 1)遍历第一个数2, target - 2 = 9 - 2 = 7
 2)判断7是否在map,发现不在,把2加入map,继续遍历
 3)直到遍历到7, target - 7 = 9 - 7 = 2
 4)判断2在map,返回正确结果
 注意,要遍历到第二个正确数.
小葫芦

No Key 的情况下,HashMap.containsKey(Key) 返回的是 false 不包括 Key.

    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

There will be no null pointer error as you think.

Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template