哈希表算法原理与 LeetCode 经典例题解析

三、面试题 01.02.判定是否互为字符重排

题目链接：面试题 01.02.判定是否互为字符重排

题目描述：

题目解析：

• 判断两个只含有小写字母的字符串，内容在排列之后是否相等。

解题思路：

• 使用一个数组，下标表示字符串的元素，数组元素表示每个元素的个数。
• 先遍历一个字符串，将元素与个数存入数组中。
• 再遍历另一个字符串，将数组中对应元素个数抵消。
• 最后看数组中是否全部为 0 即可。
• 优化思路：
  • 当数组中出现小于 0 的数组元素的时候，就代表该下标对应的字符在两个字符串中个数不一样。
  • 两个字符串长度不一样直接就返回 false。
  • 当有上一条条件的时候，就不用在遍历数组了。

// 时间复杂度：O(n)
// 空间复杂度：O(1)
import java.util.*;

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int[] hash = new int[26];
        for (int i = 0; i < s1.length(); i++) hash[s1.charAt(i) - 'a']++;
        for (int i = 0; i < s2.length(); i++) if (--hash[s2.charAt(i) - 'a'] < 0) return false;
        return true;
    }
}

四、217.存在重复元素

题目链接：217.存在重复元素

题目描述：

解题思路：

• 直接将数组中的元素，放入集合之中。
• 遍历数组，当集合中已经有该元素，符合题目条件，返回 true。
• 如果没有，就将该元素放入集合。
• 当遍历完数组，还没有找到，就返回 false。

解题代码：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
import java.util.*;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hash = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (hash.contains(nums[i])) return true;
            hash.add(nums[i]);
        }
        return false;
    }
}

五、219.存在重复元素 II

题目链接：219.存在重复元素 II

题目描述：

解题思路：

• 我们将 (数组元素 - 下标) 放入 hash 表中。
• 当我们遍历数组的时候，当集合中已经有该元素，并且下标差值小于等于 k，符合题目条件，返回 true。
• 否则，将该元素以及下标放入 hash 表中，因为我们求得是小于等于 k，所以就算关键字已经存在，那么覆盖后是后一个元素的下标，离下一个该数组元素更近。

解题代码：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
import java.util.*;

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

六、49.字母异位词分组

题目链接：49.字母异位词分组

题目描述：

题目解析：

• 将给的字符串数组中，元素排列之后相等的元素放在一堆。

解题思路：

• 我们使用 hash 表，hash 表中存储（字符串数组元素排序结果 - 结果数组元素）。
• 我们遍历字符串数组，先将该元素排序，排序后，如果 hash 表中有这个关键字，那么就添加这个字符串数组元素进 value。
• 如果没有，就先申请空间，再添加。
• 最后将 hash 表中的 value 全部返回即可。

解题代码：

// 时间复杂度：O(NlogN)
// 空间复杂度：O(n)
import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            // 字符串数组元素排序
            char[] tmp = strs[i].toCharArray();
            Arrays.sort(tmp);
            String key = new String(tmp);
            if (!hash.containsKey(key)) {
                hash.put(key, new ArrayList<>());
            }
            hash.get(key).add(strs[i]);
        }
        return new ArrayList<>(hash.values());
    }
}