哈希表
数组
442. 数组中重复的数据
思路一：快排
数组中的元素要么出现一次，要么出现两次，所以可先使用Arrays.sort，在对数组进行遍历，即比较左右两元素是否相等，相等则说明出现了两次，添加到结果集。
代码略
思路二：哈希表
以元素作为下标，统计元素的个数，个数为2则添加到结果集。这里不需要HashMap，因为数组元素的大小访问在1-n，只需要一个长度为n+1的数组。
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
int[] hash = new int[nums.length+1];
for(int num: nums) {
hash[num]++;
if(hash[num] == 2) {
res.add(num);
}
}
return res;
}
}
1394. 找出数组中的幸运数
思路：哈希表
第一次遍历，先统计各个元素出现的次数。
第二次遍历，比较元素和对应的计数是否相同，对于多个幸运数需要选取最大的，可以采用求最大值方法。
class Solution {
public int findLucky(int[] arr) {
int len=arr.length;
int[] hash = new int[501];
//哈希计数
for(int i=0;i<len;i++){
hash[arr[i]]++;
}
//查找幸运数
int max = -1;
for(int i=0; i<len; i++) {
if(hash[arr[i]] == arr[i] && max < arr[i]) {
max = arr[i];
}
}
return max;
}
}
1122. 数组的相对排序
思路：哈希表
对数组arr1的元素进行哈希统计，然后遍历arr2构造结果数组，由于arr2的元素均在arr1中，所以通过哈希表即可获得arr2中的元素在arr1中出现的次数，循环保存到结果数组即可。
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] hash = new int[1001];
//哈希计数
for (int i = 0; i < arr1.length; i++) hash[arr1[i]]++;
//map根据arr2的元素赋值给arr1(此时arr1已经没用了，所以可以作为结果数组使用)
int idx = 0;
for (int i = 0; i < arr2.length; i++) {
while (hash[arr2[i]] > 0) {//循环保存
hash[arr2[i]]--;
arr1[idx++] = arr2[i];
}
}
//遍历map中剩余的元素
for (int i = 0; i < hash.length; i++){
while (hash[i] > 0) {
hash[i]--;
arr1[idx++] = i;
}
}
return arr1;
}
}
字符串
面试题 01.02. 判定是否互为字符重排
思路：哈希表
对字符串s1采用加法的方式统计字符的出现次数，对s2则采用减法的方式统计。例如a在s1中出现3次，在s2中也出现3次，那么最终哈希表中a的计数为0，如果中间存在计数小于0的字符，则说明结果为false
由于该题的测试用例仅仅只包含26字母，所以也可用数组作为哈希表
class Solution {
public boolean CheckPermutation(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
Map<Character, Integer> map = new HashMap<>();
//加法统计
for (int i = 0; i < s1.length(); i++) {
map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0) + 1);
}
//减法统计
for (int i = 0; i < s2.length(); i++) {
map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0) - 1);
if (map.getOrDefault(s2.charAt(i), -1) < 0) {
return false;
}
}
return true;
}
}
提示：getOrDefault跟get一样，只是当map中不存在时，它能返回自定义默认值，而不是null
