【练习】哈希表的使用
- 🎥 个人主页：Dikz12
- 🔥个人专栏：算法(Java)
- 📕格言：吾愚多不敏，而愿加学
- 欢迎大家👍点赞✍评论⭐收藏
目录
1.哈希表简介
2.两数之和
题目描述
题解
代码实现
2.面试题.判定是否互为字符重排
题目描述
题解
代码实现
3.存在重复元素
题目描述
题解
代码实现
4.存在重复元素 II
题目描述
题解
代码实现
5.字母异位词分组
题目描述
题解
代码实现
1.哈希表简介
- 哈希表是什么？
存储数据的容器。
- 有什么用 ？
快速查找某个元素，时间复杂度可以达到 O(1)。
- 什么时候用哈希表？
当出现频繁查找某一个数的场景时。
- 怎么用哈希表？
1.容器（哈希表 HashMap）
2.用数组模拟简易的哈希表。如：字符串中的字符，数据范围很小的时候。
2.两数之和
题目描述
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
题解
解法一：暴力枚举. O(n^2)
- 先固定其中一个数.
- 依次与该数之前的数相加.
解法二： 使用哈希表来优化. O(n)
- 可以事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中，然后直接在哈希表中查找每⼀个元素的 target - nums[i] ，就能快速的找到⽬标和的下标.
- 这⾥有⼀个⼩技巧，可以不⽤将元素全部放⼊到哈希表之后，再来⼆次遍历；⽽是在将元素放⼊到哈希表中的同时，直接来检查表中是否已经存在当前元素所对应的⽬标元素（即 target - nums[i] ）。
代码实现
public int[] twoSum(int[] nums, int target) {
//<value, i>
Map<Integer, Integer> hash = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
int ret = target - nums[i];
if(hash.containsKey(ret)) {
return new int[]{i, hash.get(ret)};
}
hash.put(nums[i], i);
}
return new int[]{-1, -1};
}2.面试题.判定是否互为字符重排
题目描述
题解
解法：使用哈希表.
算法思路：
- 当两个字符串的⻓度不相等的时候，是不可能构成互相重排的，直接返回 false ；
- 如果两个字符串能够构成互相重排，那么每个字符串中各个字符出现的次数⼀定是相同 的。因此，我们可以分别统计出这两个字符串中各个字符出现的次数，然后逐个⽐较是否相等即可。这样的话，我们就可以选择「哈希表」来统计字符串中字符出现的次数。
代码实现
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 j = 0; j < s2.length(); j++) {
hash[s2.charAt(j) - 'a']--;
if(hash[s2.charAt(j) - 'a'] < 0) {
return false;
}
}
return true;
}3.存在重复元素
题目描述
给你一个整数数组
nums。如果任一值在数组中出现 至少两次 ，返回true；如果数组中每个元素互不相同，返回false。示例 1：
输入：nums = [1,2,3,1] 输出：true示例 2：
输入：nums = [1,2,3,4] 输出：false
题解
算法思路：（和两数之和的逻辑一样）
- 仅需在遍历数组的过程中，检查当前元素「是否在之前已经出现过」即可。
-
可以利⽤哈希表，仅需存储数「组内的元素」。在遍历数组的时候，⼀边检查哈希表中是否已经出现过当前元素，⼀边将元素加⼊到 哈希表中。
代码实现
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;
}4.存在重复元素 II
题目描述
给你一个整数数组
nums和一个整数k，判断数组中是否存在两个 不同的索引i和j，满足nums[i] == nums[j]且abs(i - j) <= k。如果存在，返回true；否则，返回false。示例 1：
输入：nums = [1,2,3,1], k = 3 输出：true示例 3：
输入：nums = [1,2,3,1,2,3], k = 2 输出：false
题解
算法思路：
解决该问题需要我们快速定位到两个信息：
- 两个相同的元素；
- 这两个相同元素的下标。
因此，我们可以使⽤「哈希表」，令数组内的元素做
key
值，该元素所对应的下标做
val
值，将
「数组元素」和「下标」绑定在⼀起，存⼊到「哈希表」中。
代码实现
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])) {
int ret = hash.get(nums[i]);
if(i - ret <= k) {
return true;
}
}
hash.put(nums[i], i);
}
return false;
}5.字母异位词分组
题目描述
题解
算法思路：
互为字⺟异位词的单词有⼀个特点：将它们
排序
之后，两个单词应该是
完全相同
的。 所以，我们可以利⽤这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同⼀ 组中。
利⽤语⾔提供的「容器」的强⼤的功能就能实现这两点：
- 将排序后的字符串（ string ）当做哈希表的 key 值；
- 将字⺟异位词数组（ string[] ）当成 val 值。
代码实现
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> hash = new HashMap<>();
for(String s : strs) {
char[] tmp = s.toCharArray();
//排序
Arrays.sort(tmp);
String key = new String(tmp);
//哈希表中不存在
if(!hash.containsKey(key)) {
hash.put(key, new ArrayList());
}
//存在
hash.get(key).add(s);
}
//提取结果
return new ArrayList(hash.values());
}