LeetCode T1 两数之和

开始做题了！学习了java中 hash map的用法。

时间复杂度的分析

暴力搜索的情况下，对每个元素都要遍历一遍剩下的其他元素，复杂度是$$O（n^2）$$。但如果采用哈希表，对每个元素$$nums[i]$$，都要从哈希表里查找是否存在$$target-nums[i]$$，这个操作的复杂度是$$O(1)$$,因此对所有元素都执行一遍是$$O(n)$$.

不用考虑是怎么插入的……反正从哈希表里get/put/containsKey都是O(1)。常数倍之后还是O(1)。

Java中的HashMap

• HashMap<K,V>：存储数据采用的哈希表结构，元素的存取顺序不能保证一致。由于要保证键的唯一、不重复，需要重写键的hashCode()方法、equals()方法。

• 创建Hashmap

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

Map接口中的常用方法

• get(Object key)

  根据key获得value。

• put(K key,V value)

  添加键值对。

• remove(Object key)

  根据key删除元素，会返回key对应的value值。

• size()

  返回HashMap中的元素数量。

• containsKey()

  检查hashMap中是否存在指定的key。

• containsValue()

  检查hashMap中是否存在指定的value。