本文共 2266 字，大约阅读时间需要 7 分钟。

对LeetCode中几道关于哈希表问题进行总结：

题目描述：

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

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

解题思路：

经典的LeetCode第一题，刚刷LeetCode时开始刷的第一道!!，刚开始时用两个for循环暴力解决，时间复杂度大，这次用哈希表，一次遍历即可完成，速度和空间都比较好。使用HashMap存储数组元素和索引，然后进行遍历判断map中是否存在target-nums[i]，若存在，则返回就是，若不存在，则往map添加相应的键值。方法的时间复杂度为 O(N)，空间复杂度为 O(N)。

class Solution {
       public int[] twoSum(int[] nums, int target) {
           HashMap
   
     map = new HashMap<>();           for (int i = 0; i 
   

题目描述：

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

输入: [1,1,1,3,3,4,3,2,4,2]输出: true输入: [1,2,3,4]输出: false

解题思路：

方法一：利用Set里面包含的元素不重复的性质来解题。

class Solution {
       public boolean containsDuplicate(int[] nums) {
           Set
   
     set = new HashSet<>();        for (int num : nums) {
               set.add(num);        }        return set.size() < nums.length;    }}
   

方法二：可以先对其进行排序，然后再判断，这样时间和空间都稍微快点

class Solution {
       public boolean containsDuplicate(int[] nums) {
           Arrays.sort(nums);        for(int i = 0; i < nums.length - 1; i++) {
               if (nums[i] == nums[i+1]) {
                   return true;            }        }        return false;    }}

题目描述：

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

输入: [1,3,2,2,5,2,3,7]输出: 5原因: 最长的和谐数组是：[3,2,2,2,3].

解题思路：

利用map API中的 getOrDefault 方法对每个数字先进行频率统计，然后再用 keySet 遍历map，若包含i + 1的话，则有和谐子序列。要掌握map中对这三个方法的运用。

• boolean containsKey(Object key)
• Set keySet()
• default V getOrDefault(Object key,V defaultValue) 若存在key，则返回map.get(key)的值，若不存在，则返回defaultValue 的值。

class Solution {
       public int findLHS(int[] nums) {
           Map
   
     map = new HashMap<>();        for (int i : nums) {
               map.put(i,map.getOrDefault(i,0)+1);	//统计每个数字出现次数        }        int longest = 0;        for (int i : map.keySet()) {
               if (map.containsKey(i+1)) {
   		//如果有和谐子序列                longest = Math.max(longest,map.get(i+1) + map.get(i));            }        }        return longest;    }}
   

关于哈希这类题目，要多熟悉HashMap 和 HashSet 的API，熟悉各种方法的运用。

SET 常用API：

转载地址：http://rerwi.baihongyu.com/