1、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

方法二：哈希表 思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
        
        // 1. 创建哈希表（字典），key 存储数组元素的值，value 存储该值对应的下标
        // 语法：Map 是接口，HashMap 是具体实现
        // 泛型 <Integer, Integer> 表示 key 和 value 都是整数
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        
        // 2. 遍历数组，i 是当前下标，nums[i] 是当前值
        // nums.length 表示数组长度
        for (int i = 0; i < nums.length; i++) {
            
            // 3. 计算目标值与当前元素的差值
            // 如果这个差值已经存在于哈希表中，说明之前遍历过的某个数可以和当前数配对
            // containsKey() 判断哈希表中是否存在某个 key
            if (hashtable.containsKey(target - nums[i])) {
                
                // 4. 找到了！
                // 返回一个数组：第一个元素是哈希表中保存的下标（之前那个数的位置），
                // 第二个元素是当前下标 i
                // get() 用于根据 key 获取对应的 value（即之前那个数的下标）
                return new int[]{hashtable.get(target - nums[i]), i};
                
            }
            
            // 5. 如果没找到配对，把当前数的值和下标存进哈希表
            // 放进去供后续元素配对使用
            hashtable.put(nums[i], i);
            
        }
        
        // 6. 理论上题目保证一定有解，这里只是为了语法完整而返回空数组
        // new int[0] 是创建一个长度为 0 的数组
        return new int[0];
        
    }

}

LeetCode Hot 100 Java

1、两数之和