about Two Sum of leetcode (HashMap)

2019-11-06 06:06:21

字体：大中小

来源：转载

供稿：网友

作个人记录LeetCode解题过程中的一些启发之用。

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

给出一个int型数组，和一个目标（和）target，返回数组中和为target的两int型数组元素的下标 实现上述功能。 Example：

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

这是一个很简单的题目,很容易实现，不过算法的时间复杂度值得考究。开始随手写的方法如下，java实现：

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

上面的算法时间复杂度为O(n2)，虽然accepted,显然不理想

得票数第一的Java实现，时间复杂度为O(n):

public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i])) { result[1] = i + 1; result[0] = map.get(target - numbers[i]); return result; } map.put(numbers[i], i + 1); } return result;}

这里用了HashMap数据结构，Java中HashMap的containsKey、get、put方法时间复杂度为O(1)（在HashMap中的存储的entry对的Key的哈希不相等时，即不发生碰撞情况）

与上面第一种算法的两层for循环相比，这种算法只需要遍历nums[]数组一次，将其以（nums[] , index）键值对存进HashMap。并且是先移动下标i，再判断containsKey()，再将其put进HashMap，再移动下标，在前面生成的HashMap中进行containsKey判断。

Key:

这种在靠后点判断之前点的方法与第一种暴力检索的在靠前点遍历之后点的思路是完全相反的，这也是由HashMap的通过hashcode()来search的性质决定的，对于nums[]规模较大时，HashMap的效率要远优于两层遍历方法。

此外还有Python实现的版本

class Solution(object): def twoSum(self, nums, target): if len(nums) <= 1: return False buff_dict = {} for i in range(len(nums)): if nums[i] in buff_dict: return [buff_dict[nums[i]], i] else: buff_dict[target - nums[i]] = i

同样时间复杂度为O(n)，这里采用的是python里的dict字典数据结构。遍历nums[]，先判断nums[i],再将target-nums[i]存进dict，直到在nums[]中遍历到在dict中存储过的元素。

总结

无论是Java还是Python实现，都是基于使用一种search时间复杂度低(O(1))的数据结构来存储数组nums[]，因为数组nums[]的search只能基于遍历这种暴力方法，时间复杂度为O(n)。因此以后在涉及到search的问题时应当选择时间复杂度更优的HashMap之类的数据结构。

about HashMap :

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。 HashMap 's Methods