LeetCode入门算法之两数之和

小灰灰 2020-11-01 07:45 614阅读 0赞

难度：简单

题目：给定一个整数数组name和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：给定 nums = 【2，7，11，15】，target = 9

因为num\[0\] + nums\[1\] = 2+7=9

所以返回【0，1】

思路：

*  利用java现有集合类的特性和方法
 *  尽量减少循环的使用已经尽量减少新建变量以提高程序运行效率

解决方案1：

撞兔法-->轮询数组中每一个元素并且和后面的元素比较。优点是：易理解 。缺点是：运行效率低。

public static int[] calculateB(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] == target - nums[i]) {
                        return new int[]{i, j};
                    }
                }
            }
            return null;
        }

解决方案2：

二哈法（两遍哈希表）-->**哈希表是保持数组中的每个元素与其索引相互对应的最好方法**。

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums\[i\]）是否存在于表中。注意，该目标元素不能是 nums\[i\]本身！

public static int[] calculateC(int[] nums, int target) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], i);
            }
            for (int i = 0; i < nums.length; i++) {
                int complement = target - nums[i];
                // map.containsKey()方法是用来检查此映射是否包含指定键的映射关系。
                if (map.containsKey(complement) && map.get(complement) != i) {
                    return new int[]{i, map.get(complement)};
                }
            }
            return null;
        }

代码段解析：

以上代码最核心的部分在于map.containsKey()这个方法，那么这个方法是什么意思？我们又可以在什么情景下使用它呢？

以下是java.util.HashMap.containsKey()方法的声明:

public boolean containsKey(object key)

其中参数key是其是否存在于此映射，是要测试的键值。也就是说，这个key比较的其实是当前map中的key的集合，如果存在返回true，不存在则返回false。与此方法相仿的方法还有：

public boolean containsValue(object value)

这时参数value比较的就是map中的value集合了。

代码学习之进阶版：

如鄙人一样好奇心比较强的童鞋们可以翻看一下HashMap的源码，看到containsKey()方法的源码如下所示：

/**
         * Returns <tt>true</tt> if this map contains a mapping for the
         * specified key.
         *
         * @param   key   The key whose presence in this map is to be tested
         * @return <tt>true</tt> if this map contains a mapping for the specified
         * key.
         */
    public boolean containsKey(Object key) {
            return getNode(hash(key), key) != null;
        }

其实方法只有一个就是getNode()方法，我们接着瞧瞧getNode()方法是如何编写的：

/**
         * Implements Map.get and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @return the node, or null if none
         */
        final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

上面的这个方法看着好像很高端，但是仔细瞅瞅也就那么回事，懂点基础的都能看懂，接下来解释一下当前代码段的精髓，也就是关键点在于：

*  返回值Node<K,V> 是什么

/**
         * Basic hash bin node, used for most entries.  (See below for
         * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
         */
        static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

经过阅读以上源码可知，**Node<K,V>其实就是一个存放有key和value的链表节点。**再看Node<K,V>中的四个属性。K 和 V相当map中的于key和value，hash是通过内部算法得到的Node对象的哈希值，next相当于C中的指针。

*  tab = table中的table是什么

/**
         * The table, initialized on first use, and resized as
         * necessary. When allocated, length is always a power of two.
         * (We also tolerate length zero in some operations to allow
         * bootstrapping mechanics that are currently not needed.)
         */
        transient Node<K,V>[] table;

table是Node<K,V>数组，这里的Node<K,V>则是某一hash值链表的头节点（不同key的hash值可能重复，将会被存放在后续的节点中）。值得注意的是，**数组table的长度是2的倍数**。

经过对以上源码的阅读，可以了解到，containsKey()方法的核心算法就是hash算法，甚至可以说HashMap等集合类的核心算法都是hash算法。

解决方案3：

一遍哈希表

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

public static int[] calculateD(int[] nums, int target) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                int complement = target - nums[i];
                // 如果complement存在于map中
                if (map.containsKey(complement)) {
                    return new int[]{map.get(complement), i};
                }
                map.put(nums[i], i);
            }
            return null;
        }

方法3与方法2的区别是，方法3只遍历了一次hash表，重中之重的是，方法3将判断放在了map.put()之前。方法3与方法1的区别是，利用map只遍历一次，方法2的第二层循环用“先判断后添值”的巧妙方法避开。

总结：

LeetCode上一道计算两数之和的简单算法，其背后的故事竟然如此之多。题刷的多了，在平时写代码的时候确实会有不同的想法，自己也会追求更简洁更高效的代码。学习是没有止境的。