LeetCode中有关哈希表问题

哈希表

LeetCode

发布日期: 2019-06-02

文章字数: 874

阅读时长: 3 分

阅读次数:

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

1.两数之和

题目描述：

给定一个整数数组 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<Integer,Integer> map = new HashMap<>();   
        for (int i = 0; i <nums.length; i++) {
            if (map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            } else {
                map.put(nums[i],i);     
            }
        }
        return new int[]{};
    }
}

217. 存在重复元素

题目描述：

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

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

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

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

解题思路：

方法一：利用Set里面包含的元素不重复的性质来解题。
时间复杂度：O（N），空间复杂度：O（N）
在这里插入图片描述

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

方法二：可以先对其进行排序，然后再判断，这样时间和空间都稍微快点
时间复杂度：O（N lg N），内存：O（1）

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;
    }
}

594. 最长和谐子序列

题目描述：

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是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<Integer,Integer> 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;
  }
}