线性搜索：哈希表

题目描述

给定一个整数数组和一个目标值，找出数组中和目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。示例：

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]复制代码

思路与实现

按题意，对一个数组元素，需找到另一个互补数。问题的本质是，查找指定值是否存在于数组中。查找问题，理应想到查找为O(1) 复杂度的哈希表。

遍历数组将 元素值=>索引 的映射关系写入 map，之后遍历查找互补的数。实现：

// 方法一：两遍哈希遍历private int[] twoSum(int[] nums, int target) {        Map
    
      map = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            map.put(nums[i], i);        }        for (int j = 0; j < nums.length; j++) {            int complement = target - nums[j];            if (map.containsKey(complement) && map.get(complement) != j) {                return new int[]{j, map.get(complement)};            }        }        throw new IllegalArgumentException("No two sum solution");    }    // 一遍哈希表    public int[] twoSum2(int[] nums, int target) {        Map
     
       map = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            int complement = target - nums[i];            if (map.containsKey(complement)) {                return new int[]{map.get(complement), i};            }            map.put(nums[i], i);        }        throw new IllegalArgumentException("No two sum solution");    }复制代码
     
    

总结

理解并抽象出本质，再选择最为合适的数据结构实现。

哈希表的增删查复杂度都是O(1)级别的，十分适合线性查找的问题。