理论

哈希表是根据关键码的值而直接进行访问的数据结构。也称为散列表

数组就是一个哈希表。

需要快速判断一个元素是否出现在集合里面时，需要考虑使用哈希法。

有效的字母异位词 leetcode-242

/*** leetcode-242. 有效的字母异位词* @param s* @param t* @return*/
public boolean isAnagram(String s, String t) {int[] sArray = new int[26]; //默认是0for(char c : s.toCharArray()){sArray[c-'a']++;}for(char c : t.toCharArray()){sArray[c-'a']--;}for (int i = 0; i < sArray.length; i++) {if(sArray[i] != 0){ //若有元素不为0，则两者中每种字符的个数有差异，多或少return false;}}return true;
}

赎金信 leetcode-383

/*** leetcode-383 赎金信* @param ransomNote* @param magazine* @return*/
public boolean canConstruct(String ransomNote, String magazine) {int[] ransomArray = new int[26]; //默认是0for(char c : ransomNote.toCharArray()){ransomArray[c-'a']++;}for(char c : magazine.toCharArray()){if(ransomArray[c-'a'] != 0){ //只统计ransom中有的字母ransomArray[c-'a']--;}}for (int i = 0; i < ransomArray.length; i++) {if(ransomArray[i] != 0){return false;}}return true;
}

字母异位词分组 leetcode-49

/*** 字母异位词分组* @param strs* @return*/
public List> groupAnagrams(String[] strs) {Map> map = new HashMap>();for (String str : strs) {char[] cArray = str.toCharArray();Arrays.sort(cArray); //给字符数组排序(位置虽然不同，但排序后一定是相同的)String key = new String(cArray);List list = map.getOrDefault(key, new ArrayList());list.add(str);map.put(key,list); //java中的map在键相同时会直接抵消}return new ArrayList>(map.values());
}

找到字符串中所有字母异位词 leetcode-438

方法1：

/*** 438. 找到字符串中所有字母异位词* （易于理解，但时间复杂度高）** @param s* @param p* @return*/
public List findAnagrams(String s, String p) {char[] sArray = s.toCharArray();char[] pArray = p.toCharArray();int[] charArray = new int[26];for (char c : pArray) {charArray[c - 'a']++;}List list = new ArrayList<>();for (int i = 0; i < sArray.length; i++) {if (i > sArray.length - pArray.length) break;int temp[] = Arrays.copyOf(charArray, charArray.length); //数组是对象，不能直接赋值boolean flag = true;for (int j = i; j < i + pArray.length; j++) {temp[sArray[j] - 'a']--;}for (int k = 0; k < temp.length; k++) {if (temp[k] != 0) {flag = false;}}if (flag) list.add(i);}return list;
}

方法2：滑动窗口

/*** 438. 找到字符串中所有字母异位词* 滑动窗口* 时间 9 ms击败 61.47%* @param s* @param p* @return*/
public List findAnagrams2(String s, String p) {int sLen = s.length();int pLen = p.length();if (sLen < pLen) return new ArrayList<>();int[] needs = new int[26];int[] window = new int[26];for (char c : p.toCharArray()) {needs[c - 'a']++;}int count = 0;for (int i = 0; i < needs.length; i++) { //统计needs的实际大小 例如“aa”，实际大小为1if (needs[i] != 0) count++;}List list = new ArrayList<>();int left = 0, right = 0, valid = 0;while (right < s.length()) {char c = s.charAt(right);right++;if (needs[c - 'a'] != 0) {window[c - 'a']++;if (window[c - 'a'] == needs[c - 'a']) {valid++;}}if (right - left == p.length()) {if (valid == count) {list.add(left);}char d = s.charAt(left);left++;if (needs[d - 'a'] > 0) {if (window[d - 'a'] == needs[d - 'a']) {valid--;}window[d - 'a']--;}}}return list;
}

方法3：速度最快，完全匹配（顺序不考虑），窗口大小固定，个人认为这种方法更好理解

/*** 438. 找到字符串中所有字母异位词* 把窗口大小固定更易于理解** @param s* @param p* @return*/
public List findAnagrams3(String s, String p) {int sLen = s.length();int pLen = p.length();if (sLen < pLen) return new ArrayList<>();int[] needs = new int[26];int[] window = new int[26];for (int i = 0; i < pLen; i++) {needs[p.charAt(i)-'a']++;window[s.charAt(i)-'a']++;}List list = new ArrayList<>();int left = 0, right = pLen - 1;if (Arrays.equals(needs, window)) list.add(0); //可能0下标就相同while (right < sLen-1) { //下面right往后移动，这里要减1，不然下面数组越界//右边界往后移right++;window[s.charAt(right) - 'a']++;//左边界往后移window[s.charAt(left) - 'a']--;left++;if (Arrays.equals(needs, window)) {list.add(left);}}return list;
}

两个数组的交集 leetcode-349

方法1:

/*** 349. 两个数组的交集* 时间* 1 ms* 击败* 98.73%* @param nums1* @param nums2* @return*/
public int[] intersection(int[] nums1, int[] nums2) {int[] arr2 = new int[1000];int[] ans = new int[1000];for (int i : nums2) {arr2[i]++;}int size = 0;for (int i = 0; i < nums1.length; i++) {if(arr2[nums1[i]] != 0 && ans[nums1[i]] ==0){ans[nums1[i]]++;size++;}}int[] res = new int[size];int index = 0;for (int i = 0; i < ans.length; i++) {if(ans[i]!=0){res[index++]=i;}}return res;
}

方法2：

/*** 时间* 0 ms* 击败* 100%* @param nums1* @param nums2* @return*/
public int[] intersection2(int[] nums1, int[] nums2) {int[] map = new int[1000];List list = new ArrayList<>(); //因为不知道结果数组有多大，所以先用list存for (int i : nums1) {map[i]++;}for (int i : nums2) {if(map[i] != 0){list.add(i);map[i] = 0;  //删除索引，防止有相同元素时，重复添加}}int[] ans = new int[list.size()];for (int i = 0; i < list.size(); i++) {ans[i] = list.get(i);}return ans;
}

两个数组的交集 II leetcode-350

/**** 时间* 0 ms* 击败* 100%* 350. 两个数组的交集 II 与上一题相比，该题可以统计重复的，但是两个数组中元素重复的次数不一样时，取小* @param nums1* @param nums2* @return*/
public int[] intersect(int[] nums1, int[] nums2) {int[] map = new int[1001];for (int i : nums1) {map[i]++;}int[] ans = new int[Math.max(nums1.length, nums2.length)];int j = 0;for (int i : nums2) {if(map[i] > 0){ans[j++] = i;map[i]--;  //索引减1}}return Arrays.copyOfRange(ans, 0, j);
}

快乐数 leetcode-202

方法1：

/*** 202 快乐数* 用时1ms* @param n* @return*/
public boolean isHappy(int n){Set set = new HashSet<>();while ( n!=1 && !set.contains(n)){set.add(n);n = nextNum(n);}return n==1;
}
public int nextNum(int n){int sum = 0;while (n > 0){int temp = n%10;sum+=temp*temp;n=n/10;}return sum;
}

方法2：

public boolean isHappy2(int n){int slow = n,fast = n; //类比于链表找环，设置快慢指针do{slow = nextNum(slow);fast = nextNum(fast);fast = nextNum(fast);}while (slow != fast);return slow  == 1;
}

两数之和 leetcode-1

/*** 两数之和 leetcode-1* @param nums* @param target* @return*/
public int[] twoSum(int[] nums, int target) {Map map = new HashMap<>();int[] res = new int[2];int i;for (i = 0; i < nums.length; i++) {int temp = target - nums[i];if (!map.containsKey(temp)) {map.put(nums[i], i);} else {res[0] = i;res[1] = map.get(temp);break;}}return res;
}

四数相加II leetcode-454

/*** 四数相加* @param nums1* @param nums2* @param nums3* @param nums4* @return*/
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map map1 = new HashMap<>();for (int i : nums1) {for (int j : nums2) {map1.put(i+j,map1.getOrDefault(i+j,0)+1); //统计任意两个数和的次数}}int count = 0;for (int i : nums3) {for (int j : nums4) {int temp = 0-(i+j);if(map1.containsKey(0-(i+j))){count+=map1.get(0-(i+j));}}}return count;
}

三数之和 leetcode-15

/*** 三数之和 leetcode-15* @param nums* @return*/
public List> threeSum(int nums[]) {List> res = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {if (nums[i] > 0) return res;if (i >0 && nums[i] == nums[i - 1]) continue; //去重int left = i+1,right = nums.length-1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if(sum >0){right--;} else if (sum < 0) {left++;}else{res.add(Arrays.asList(nums[i],nums[left],nums[right]));while (left left++;}while (left right--;}right--;left++;}}}return res;
}

四数之和 leetcode-18

public List> fourSum(int[] nums, int target) {List> list = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length - 3; i++) {if (nums[i] > 0 && nums[i] > target) {return list;}if (i > 0 && nums[i] == nums[i - 1]) {continue;  //去重}for (int j = i + 1; j < nums.length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue; // 超过i+1才属于j的部分}int left = j + 1, right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum < target) {left++;} else if (sum > target) {right--;} else {list.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));left++;while (left < right && nums[left] == nums[left - 1]) {left++;}right--;while (left < right && nums[right] == nums[right + 1]) {right--;}}}}}return list;
}