代码随想录 刷题攻略 笔记1.关于哈希表，你该了解这些！2.哈希表：可以拿数组当哈希表来用，但哈希值不要太大
242.有效的字母异位词 3.哈希表：查找常用字符
1002. 查找常用字符 4.哈希表：哈希值太大了，还是得用set
349. 两个数组的交集小结 5.哈希表：用set来判断快乐数
202. 快乐数小结 6.哈希表：map等候多时了
1. 两数之和 7.哈希表：其实需要哈希的地方都能找到map的身影
第454题.四数相加II 8.哈希表：这道题目我做过？
383. 赎金信 9.哈希表：解决了两数之和，那么能解决三数之和么？
第15题. 三数之和 10.双指针法：一样的道理，能解决四数之和
第18题. 四数之和小结
核心代码 11.哈希表：总结篇！（每逢总结必经典）
代码随想录 刷题攻略 笔记代码随想录 刷题攻略
代码随想录 刷题攻略 笔记
讲义地址
2.哈希表：可以拿数组当哈希表来用，但哈希值不要太大讲义地址
242.有效的字母异位词leetcode地址
输入字符有限且比较小，使用数组比hashmap快。
class Solution {
public boolean isAnagram(String s, String t) {
int sLen = s.length();
int tLen = t.length();
if(sLen != tLen){
return false;
}
char temp = 0;
Map map = new HashMap<>();
for (int i = 0; i < sLen; i++) {
temp = s.charAt(i);
map.put(temp, map.getOrDefault(temp,0) + 1);
}
for (int i = 0; i < tLen; i++) {
temp = t.charAt(i);
if(!map.containsKey(temp)){
return false;
}
map.put(temp, map.get(temp) - 1);
if(map.get(temp) < 0){
return false;
}
}
return true;
}
}
3.哈希表：查找常用字符
讲义地址
1002. 查找常用字符leetcode地址
class Solution {
public List commonChars(String[] words) {
int[] minfreq = new int[26];
Arrays.fill(minfreq, Integer.MAX_VALUE);
// 用一个26位的数组记录字母在这么多个词中的最低频率
for (String word : words) {
int[] freq = new int[26];
int length = word.length();
for (int i = 0; i < length; ++i) {
char ch = word.charAt(i);
++freq[ch - 'a'];
}
for (int i = 0; i < 26; ++i) {
minfreq[i] = Math.min(minfreq[i], freq[i]);
}
}
// 打印26个字母的最低频率
List ans = new ArrayList();
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < minfreq[i]; ++j) {
ans.add(String.valueOf((char) (i + 'a')));
}
}
return ans;
}
}
4.哈希表：哈希值太大了，还是得用set
讲义地址
349. 两个数组的交集leetcode地址
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length;
int length2 = nums2.length;
int[] temp = new int[length1 > length2 ? length2 : length1];
int index0 = 0;
int index1 = 0;
int index2 = 0;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1];
int num2 = nums2[index2];
if (num1 < num2) {
index1++;
} else if (num1 > num2) {
index2++;
} else {
if (index0 == 0 || num1 != temp[index0 - 1]) {
temp[index0] = num1;
index0++;
}
index1++;
index2++;
}
}
return Arrays.copyOfRange(temp, 0, index0);
}
}
小结
先排序+集合比map要快。
使用双指针
关键：
if (index0 == 0 || num1 != temp[index0 - 1]) {
temp[index0] = num1;
index0++;
}
5.哈希表：用set来判断快乐数
讲义地址
202. 快乐数leetcode地址
class Solution {
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getNext(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getNext(slowRunner);
fastRunner = getNext(getNext(fastRunner));
}
return fastRunner == 1;
}
}
小结
使用快慢指针判断是否有环，这比使用set更节省空间。
6.哈希表：map等候多时了讲义地址
1. 两数之和leetcode地址
class Solution {
public int[] twoSum(int[] nums, int target) {
Map hashtable = new HashMap();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
7.哈希表：其实需要哈希的地方都能找到map的身影
讲义地址
第454题.四数相加IIleetcode地址
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap hashMap = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
hashMap.put(nums1[i] + nums2[j], hashMap.getOrDefault(
nums1[i] + nums2[j], 0) + 1);
}
}
int res = 0;
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
if (hashMap.containsKey(-nums3[i] - nums4[j])) {
res += hashMap.get(-nums3[i] - nums4[j]);
}
}
}
return res;
}
}
8.哈希表：这道题目我做过？
讲义地址
383. 赎金信leetcode地址
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()) {
return false;
}
HashMap map = new HashMap<>();
for (int i = 0; i < magazine.length(); i++) {
char temp = magazine.charAt(i);
map.put(temp, map.getOrDefault(temp,0)+1);
}
for (int i = 0; i < ransomNote.length(); i++) {
char temp = ransomNote.charAt(i);
if (map.containsKey(temp)){
map.put(temp,map.get(temp)-1);
if (map.get(temp) ==0){
map.remove(temp);
}
}else {
return false;
}
}
return true;
}
}
如果使用数组来计数，而不是使用hashmap，效率会更高。
讲义地址
第15题. 三数之和leetcode地址
class Solution {
public List> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
List> res = new ArrayList<>();
if (nums == null || nums.length < 3) return res;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// target必须大于0
if (nums[i] > 0) break;
// 去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
int target = -nums[i];
while (left < right) {
if (nums[left] + nums[right] == target) {
res.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
left++;
right--;
// 去重
while (left < right && nums[left] == nums[left - 1]) left++;
// 去重
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
}
return res;
}
}
10.双指针法：一样的道理，能解决四数之和
讲义地址
第18题. 四数之和leetcode地址
class Solution {
public List> fourSum(int[] nums, int target) {
List> res = new ArrayList<>();
if (nums == null || nums.length < 4) return res;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
// if (nums[i] > target) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i+1; j < nums.length - 2; j++) {
// if (nums[j] > target - nums[i]) break;
if (j>i+1 && nums[j] == nums[j-1]) continue;
int left = j + 1;
int right = nums.length - 1;
int newTarget = target-nums[i]-nums[j];
while (left < right) {
if (nums[left] + nums[right] == newTarget) {
res.add(new ArrayList<>(Arrays.asList(nums[i],nums[j], nums[left], nums[right])));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[left] + nums[right] < newTarget) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}
小结
这题与上一题解法一样
核心代码就是上一题的代码
11.哈希表：总结篇！（每逢总结必经典）讲义地址
