目录
1、1.两数之和
1.1 算法原理
- 解法一: 暴力求解. 固定一个数, 向前/向后 查找另个一数, 判断是否两数之和为 target
- 解法二: 哈希优化. 从前向后遍历数组, 每遍历一个元素 nums[i] , 从哈希表中找有没有 target - nums[i] 这个元素, 如果有则返回结果. 如果没有, 再把当前数和其下标绑定放入哈希表中.
注意, 是在遍历的过程中将当前元素和下标放入哈希中, 而不是 "一口气" 全部放入哈希表中, 否则可能重复使用一个元素.
1.2 算法代码
class Solution {
public int[] twoSum(int[] nums, int target) {
// <nums[i], i>
Map<Integer, Integer> hash = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
int val = target - nums[i];
if(hash.containsKey(val)) {
return new int[]{i, hash.get(val)};
}else {
hash.put(nums[i], i);
}
}
// 照顾编译器
return new int[]{0, 0};
}
}2、面试题 01.02. 判定是否互为字符重排
2.1 算法原理
解法: 哈希表
使用数组自己模拟哈希表 hash[26]:
- 两个数组 hash1 + hash2 => 记录两个字符串中字符出现的个数, 如果相同字符出现的个数不相等 => false
- 优化: 一个数组 => 记录第一个字符串中字符出现的个数, 遍历第二个字符串时, 每出现一个字符, 对该字符哈希表中的值进行 -1 操作. 若最终 hash 中每个元素的值都为 0 => true, 反之 => false
2.2 算法代码
class Solution {
public boolean CheckPermutation(String s1, String s2) {
if(s1.length() != s1.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++) {
hash[s2.charAt(i) - 'a']--;
}
for(int x : hash) {
if(x != 0) return false;
}
return true;
}
}3、217. 存在重复元素
3.1 算法原理
使用哈希,
- 每遍历一个元素, 从哈希表中看看有没有相同的元素, 有的话直接返回 true. 没有的话把当前元素放到哈希中, 继续向后遍历.
- 遍历完若还没有返回, 说明整个数组中没有重复的元素 => false
3.2 算法代码
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> hash = new HashSet<>();
for (int num : nums) {
if (hash.contains(num)) return true;
else hash.add(num);
}
return false;
}
}4、219. 存在重复元素 II
4.1 算法原理
核心: 哈希表
- 从前往后遍历, 将数组元素和下标绑定, 放到哈希表中
- 每遍历一个元素, 从哈希中找有没有重复的元素, 并且下标之差小于 k
- 若发现有元素满足上述两个条件, 返回 true
- 当全部遍历完后, 没有进行返回, 则说明整个数组中没有重复的元素, 返回 false
注意: 由于 Map 天然去重的特性, 当相同的元素(Key)重复放入, 可能会发生覆盖现象.
但是本题不影响, 因为新放入的数据是最近的下标, 当后续有元素重复时, get 得到位置是最近位置.
4.2 算法代码
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]) && Math.abs(hash.get(nums[i]) - i) <= k) {
return true;
}else {
hash.put(nums[i], i);
}
}
return false;
}
}5、49. 字母异位词分组
5.1 算法原理
哈希表 => <String, List<String>>
- 将字符串进行排序:
- 如果排完序的字符串在哈希表中存在, 则说明存在字母异位词, 把原本的字符串放进 List<String> 中
5.2 算法代码
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] ch = str.toCharArray();
Arrays.sort(ch);
List<String> list = map.getOrDefault(String.valueOf(ch), new ArrayList<>());
list.add(str);
map.put(String.valueOf(ch), list);
}
return new ArrayList<>(map.values());
}
}END
标签：专题,hash,nums,int,元素,算法,哈希 From： https://blog.csdn.net/2401_83595513/article/details/143301668