今天来几道简单的哈希表题，顺带回顾一下 Java 的HashMap，HashSet的一些API

lc219. 存在重复元素 II（EZ）

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5

最简单的方法当然是暴力——两重循环，这样很快就能写出最简单的题解代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
	int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] == nums[j] && Math.abs(i - j) <= k) {
                return true;
            }
        }
    }
    return false;
}

这是最简单的解法，大一刚学会C语言的新生都知道可以这么写，但是时间复杂度非常糟糕，O(n2)O(n^2)，考虑到这道题的数据范围，非常容易就tle

那么就要考虑优化。我们知道哈希表的查找非常快，所以我们可以利用哈希表来帮助我们查找。把已经遍历过的键值对存进哈希表就可以了

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && Math.abs(map.get(nums[i]) - i) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

这样我们成功把复杂度降低到O(n)O(n)

lc242. 有效的字母异位词（EZ）

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

**注意：**若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

  • 1 <= s.length, t.length <= 5 * 10^4
  • s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

我们先不考虑进阶情况。其实，把不带进阶要求的题目解出来了，进阶的也就能跟着一起接出来了

我们知道字符串 s 和 t 都由小写字母组成，说明最多就只能出现26种不同的字符。所以我们可以用数组来代替哈希表，先遍历字符串，再遍历哈希表，查询是否存在某一个下标使得两个数组对应的值不同

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] sHash = new int[26];
        int[] tHash = new int[26];
        int len = s.length();
        for (int i = 0; i < len; i++) {
            sHash[s.charAt(i) - 'a']++;
            tHash[t.charAt(i) - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (sHash[i] != tHash[i]) {
                return false;
            }
        }
        return true;
    }
}

对于进阶要求，我的思路是这样的：unicode字符同样也是有限的（Unicode4.0规范前，utf-8编码下，unicode字符共65536个，即使是Unicode4.0规范之后，unicode编码的字符数量仍然是有限的），并且，unicode字符的编码同样也是int类型，所以我们可以也用数组来代替哈希表

但是这样有一个很大的缺点——我们不一定有很多数据要存储，但是我们却开辟了过大的数组空间，例如，我们至少要开辟65536 * 2byte * 2 字节的数组空间，这样的话内存占用会非常大。虽然我们都说要 ”空间换时间“，但是对于这种无用的空间浪费，很显然我们是可以避免的

所以实际上，如果真的要完成进阶要求，我们不能用数组，得考虑使用哈希表。哈希表的使用，在这里不再赘述

lc49. 字母异位词分组（MD）

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

因为Java中的String不能排序，所以相对于C++来讲，增加了一点不方便（这里的不方便是指做题，实际上Java的String远比C++的String好用，C++的String真的是要啥没啥），但我们也能做出来

这里的字母异位词，是指重新排列源单词的所有字母得到的一个新单词，那么说明字母异位词它们字母的出现次数应该是一样的。例如aba和aab，它们是字母异位词，a同样出现了2次，b出现了1次。所以对于异位词判定，我们可以用类似于前面提到的数组来存储字母的出现次数

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for (String str : strs) {
            int[] count = new int[26];
            int len = str.length();
            for (int i = 0; i < len; i++) {
                count[str.charAt(i) - 'a']++;
            }
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    sb.append((char)('a' + i));
                    sb.append(count[i]);
                }
            }
            String key = sb.toString();
            List<String> list = hash.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            hash.put(key, list);
        }
        return new ArrayList<List<String>>(hash.values());
    }
}

lc1. 两数之和（EZ）

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

力扣的第一道题

我第一次做这道题还是我刚刚大一入学的时候，那时候别说 Java 和 C++了，C语言都没学明白，最后还是看的题解才把这道题写出来，但还是搞不明白这道题到底要怎么做；后来我系统学了数据结构与算法，第一次用暴力法把这道题a出来，我能感受到一种成就感；再到后来，我学了C++，知道了哈希表是什么东西，第一次用哈希表把这道题a出来，也深刻感受到了什么叫做算法，什么是算法的魅力——从一般甚至最劣算法、最多的时间占用，优化到最优算法、最少的时间占用、最优秀的时间复杂度；到我后来进acm队，各种训练各种比赛，哈希表也是我经常会用到的数据结构，可以说是这道题开始了我的算法生涯吧

我印象很深刻，这道题下面有一个评论，是这样的

有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。

2万多人点赞，我也是其中的一员。被卡在第一题，简单题，甚至放到现在来说都不能叫做算法题的题，确实很可耻

不说了，讲题解。这道题大家都应该很熟悉了，不多废话，其实就是用哈希表来对已经遍历过的数据进行存储，毕竟哈希表查找速度快，数组查找速度慢

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

lc202. 快乐数（EZ）

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

  • 1 <= n <= 2^31 - 1

我最开始的解法是双指针——很明显是抄的力扣官方题解，以至于我到现在都不知道这道题用双指针要怎么做——看到这里的读者可以尝试着用双指针做这道题

还是哈希表，还是缓存已经查询过的数据

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) {
            set.add(n);
            n = getSum(n);
        }
        return n == 1;
    }

    private int getSum(int n) {
        int sum = 0;
        while (n != 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
}