基础知识
哈希 常见的结构（不要忘记数组）
- 数组
- set （集合）
- map(映射)
注意 哈希冲突 哈希函数
LeetCode 242
分析1.0
HashMap<Character, Integer> 记录字符元素及其个数，再以字符序列对key进行排序，比较两个Map是否一致或者是遍历Map1的时候，在map2中对cur指针key查询对应个数
有一个用例未通过
原因：
引用类型比较值使用equals().方法map1.get(c).equals(map2.get(c))
class Solution {
public boolean isAnagram(String s, String t) {
int sizeS = 0, sizeT = 0;
HashMap<Character,Integer> map1 = new HashMap();
HashMap<Character,Integer> map2 = new HashMap();
for(int i = 0; i < s.length(); i++){
map1.put(s.charAt(i), map1.getOrDefault(s.charAt(i),0)+1);
}
for(int j = 0; j < t.length(); j++){
map2.put(t.charAt(j), map2.getOrDefault(t.charAt(j),0)+1);
}
System.out.println(map1);
System.out.println(map2);
// 光size相同不行 要size同而且对应的元素也同
sizeS = map1.size();
sizeT = map2.size();
if(sizeS != sizeT){
return false;
}
for(Character c : map1.keySet()){
if(map2.get(c) == null){
return false;
}
if(map1.get(c) != map2.get(c)){
return false;
}
}
return true;
}
}分析2.0
数组也是一个hash表，它的key就是索引，元素就是value 要将普通的key一一对应为数组的index
LeetCode 349
分析1.0
两个数组，找他们的公共集合，集合元素不重复
思路：遍历较短数组，如果长数组中存在这个元素，加入Set，最后将Set转换成int[]
在第二个for循环中，可用contains()方法判断元素是否在集合中
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set = new HashSet();
for(int i = 0; i < nums1.length; i++){
for(int j = 0; j < nums2.length; j++){
if(nums1[i] == nums2[j]){
set.add(nums1[i]);
}
}
}
int[] ans = new int[set.size()];
int index = 0;
for(Integer temp : set){
ans[index++] = temp.intValue();
}
return ans;
}
}LeetCode 202
分析1.0
元素是正整数，分离各个位置上的元素，求和判断是否为快乐数
如何判断循环终止条件-出现无限循环数，将所有数存进set，当存在相同数时即进入循环
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet();
set.add(n);
while(true){
int val = getVal(n);
System.out.println(val);
if(val == 1){
//System.out.println(set);
return true;
}
if(set.contains(val)){
//System.out.println(set);
return false;
}else{
set.add(val);
n = val;
}
}
}
public int getVal(int n){
int ans = 0;
while(n != 0){
ans += (n%10)*(n%10);
n = n / 10;
}
return ans;
}
}分析2.0
说白了就是找到循环退出的条件，循环继续下去的条件
LeetCode 1
分析1.0
将数组元素去重存放进HashMap<Integer,Integer> （元素值，索引）达到去重功能，接着两层for循环解决问题，将结果添加进int[] ans返回
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap();
int[] ans = new int[2];
for(int i = 0; i < nums.length; i++){
map.put(nums[i], i);
}
for(Integer val1 : map.keySet()){
int cnt = 0;
for(Integer val2 : map.keySet()){
if(cnt == 0){
cnt++;
continue;
}
if(val1 + val2 == target){
ans[0] = map.get(val1).intValue();
ans[1] = map.get(val2).intValue();
return ans;
}
}
}
return ans;
}
}问题
- [3,3] 6这样的用例就不行了
- 这样遍历每次val1 val2初值是一样的
- 其实哈希表的作用就在于去重+判断是否存在某个元素 怎么利用特性去写代码还是很要紧的
for(Integer val1 : map.keySet()){
for(Integer val2 : map.keySet()){
if(val1 + val2 == target){
ans[0] = map.get(val1).intValue();
ans[1] = map.get(val2).intValue();
return ans;
}
}
}已经遍历的部分+当前遍历元素+未遍历部分
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i]; // 遍历当前元素，并在map中寻找是否有匹配的key
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);
break;
}
map.put(nums[i], i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中
}分析2.0
这题具体情况具体分析不就是一个暴力for循环能解决的事儿吗???
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ans = new int[2];
for(int i = 0; i< nums.length-1; i++){
for(int j = i+1; j < nums.length; j++){
if(nums[i] + nums[j] == target){
ans[0] = i;
ans[1] = j;
return ans;
}
}
}
return ans;
}
}分析3.0
其实就是找两个数，遍历的当前元素算一个，那剩下的肯定就只能在已经遍历或者未遍历的元素中找，暴力for循环就是在未遍历的元素中找，Map的contains就是在已经遍历过的元素中找，但是有一个很巧妙的思维就是
int temp = target - nums[i]不用像普通暴力双层for循环那样猛烈
总结
- 引用类型比较值使用equals()
- HashMap默认是按照key字典序进行存储的 可打印验证
- key - 数组下标 - value
- 字符转数字 '字符' - 'a' 得到的就是对应26个字符的序数
- 明确题目要求，有时它只需要一个结果，如何操作数据、要不要操作数据是一个问题
- Integer泛型得到的集合不能直接转成int[]
- int[] arr 必须初始化后才能进行操作 不能直接int[] arr = 另外一个数组
- Set HashMap 遍历过程 这个没法儿用xx.get(index)访问元素
- 找到循环退出的条件，循环继续下去的条件
- 查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法
- 判断特殊情况-定义返回结果-找准循环开始/结束边界条件-打日志定位错误
- 数组特殊情况
if(nums == null || nums.length == 0){ return res; } -
抽象思维 已经遍历的部分+当前遍历元素+未遍历部分 遍历过的部分存进map用contains()判断 判断的时候要知道你还缺哪个元素
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、target、res
