【java】哈希＜两数之和＞ 理解哈希

两数之和

题目描述：

        给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

---

题目分析：

如图，定义两个指针遍历，因为不能使用两次相同的元素，故 j 的初始值在 i 的后一个 。

因为每种输入只会对应一个答案，因此找到那两个整数就退出循环。

---

我的解法：

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

更优解法：哈希表

        使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

        这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}

这里我们介绍一下HashMap .

---

哈希函数

在之前的博客里，我介绍了哈希算法，这里我简单描述一下。

        为了减少无序数组查找的时间复杂度，我们先想到了有序数组的二分查找法，但是就要首先对无序数组进行排序，排序的时间复杂度大都O(n^2),O(nlogn),O(kn).而二分查找法也需要O(logn)的时间复杂度，因此不比原来少。

        我们又想到了通过某一个算法决定数据要插入的位置，位置可以=n%arr.length，这就是哈希算法。根据位置找到数据时间复杂度为O(1).    但是可能会出现不同的数值计算出来在同一个位置这种情况，这就是哈希碰撞。  我们采用的解决方法是用拉链法，在这个位置加上链表，

这就是哈希表。当链表长度不长时O(1) ,当链表很长时O(n).

HashMap

        HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

        HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

        HashMap 是无序的，即不会记录插入的顺序。

        HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。        

         HashMap 的 key 与 value 类型可以相同也可以不同，可以是字符串（String）类型的 key 和 value，也可以是整型（Integer）的 key 和字符串（String）类型的 value。

Map<String,String> map = Map.of("home","hebei","name","lojarro");

key	value
home	hebei
name	lojarro

Map<Integer,String> map = Map.of(1,"hebei",2,"lojarro");

key	value
1	hebei
2	lojarro

HashMap 中的元素实际上是对象，一些常见的基本类型可以使用它的包装类。

基本类型对应的包装类表如下：

基本类型	引用类型
boolean	Boolean
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character

 以下实例我们创建一个 HashMap 对象 Sites， 整型（Integer）的 key 和字符串（String）类型的 value：

HashMap<Integer, String> Sites = new HashMap<Integer, String>();

方法

添加键值对(key-value)可以使用 put() 方法

Sites.put(1, "Google");

get(key) 方法来获取 key 对应的 value

System.out.println(Sites.get(3));

containsKey()	检查 hashMap 中是否存在指定的 key 对应的映射关系。
containsValue()	检查 hashMap 中是否存在指定的 value 对应的映射关系。