一、哈希表

1.總結一下，當我們遇到了要快速判斷一個元素是否出現集合里的時候，就要考慮哈希法。但是哈希法也是犧牲了空間換取了時間，因為我們要使用額外的數組，set或者是map來存放數據，才能實現快速的查找。如果在做面試題目的時候遇到需要判斷一個元素是否出現過的場景也應該第一時間想到哈希法！
2.當數據量比較少時，可以考慮使用數組。直接使用set 不僅占用空間比數組大，而且速度要比數組慢，set把數值映射到key上都要做hash計算的。不要小瞧這個耗時，在數據量大的情況，差距是很明顯的。

二、有效的字母異位詞

1、有效的字母異位詞(力扣242)

//1.t是s的異位詞等價于「兩個字符串排序后相等」public static boolean isAnagram(String s, String t) {if (s.length() != t.length()){return false;}char[] c1 = s.toCharArray();char[] c2 = t.toCharArray();Arrays.sort(c1);Arrays.sort(c2);return Arrays.equals(c1,c2);}

//2.輸入字符串不包含 unicode 字符public static boolean isAnagram(String s, String t) {if (s.length() != t.length()){return false;}int[] arr = new int[26];for (int i = 0; i < s.length(); i++) {arr[s.charAt(i) - 'a'] ++;}for (int i = 0; i < t.length(); i++) {arr[t.charAt(i) - 'a'] --;if (arr[t.charAt(i) - 'a'] < 0){return false;}}return true;}

如果輸入字符串包含 unicode 字符,那就只能使用哈希表了, JAVA的char類型是支持unicode的

//3.輸入字符串包含 unicode 字符public static boolean isAnagram(String s, String t) {if (s.length() != t.length()){return false;}Map<Character,Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0) + 1);}for (int i = 0; i < t.length(); i++) {map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0) - 1);if (map.get(t.charAt(i)) < 0){return false;}}return true;}

2、贖金信(力扣383)

//1.和242很像，沒啥難度public static boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()){return false;}int[] arr = new int[26];for (int i = 0; i < magazine.length(); i++) {arr[magazine.charAt(i) - 'a'] ++;}for (int i = 0; i < ransomNote.length(); i++) {arr[ransomNote.charAt(i) - 'a'] --;if (arr[ransomNote.charAt(i) - 'a'] < 0){return false;}}return true;}

//2.哈希mappublic static boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()) {return false;}Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < magazine.length(); i++) {map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) + 1);}for (int i = 0; i < ransomNote.length(); i++) {map.put(ransomNote.charAt(i),map.getOrDefault(ransomNote.charAt(i),0) - 1);if (map.get(ransomNote.charAt(i)) < 0){return false;}}return true;}

3、字母異位詞分組(力扣49)

//1.哈希mappublic List<List<String>> groupAnagrams(String[] strs) {//考慮清楚用什么來表示鍵和值Map<String,ArrayList<String>> map = new HashMap<>();for (String s : strs){char[] c = s.toCharArray();Arrays.sort(c);String key = String.valueOf(c);if (!map.containsKey(key)){map.put(key,new ArrayList<>());}map.get(key).add(s);}//map.values() 返回的是collection，直接是集合return new ArrayList<>(map.values());}

4、找到字符串中所有字母異位詞(力扣438)

//1.自己想的public static List<Integer> findAnagrams(String s, String p) {if (s.length() < p.length()){return new ArrayList<>();}List<Integer> list = new ArrayList<>();char[] c1 = p.toCharArray();Arrays.sort(c1);for (int i = 0; i <= s.length() - p.length(); i++) {char[] c2 = s.substring(i,i + p.length()).toCharArray();Arrays.sort(c2);if (Arrays.equals(c1,c2)){list.add(i);}}return list;}

//2.滑動窗口public static List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length();if (sLen < pLen) {return new ArrayList<>();}//分別統計滑動窗口和p中的字符的數量int[] sCount = new int[26];int[] pCount = new int[26];List<Integer> list = new ArrayList<>();for (int i = 0; i < pLen; i++) {sCount[s.charAt(i) - 'a']++;pCount[p.charAt(i) - 'a']++;}if (Arrays.equals(sCount, pCount)) {list.add(0);}//滑動窗口向右移動，依次比較for (int i = 0; i < sLen - pLen; i++) {sCount[s.charAt(i) - 'a'] --;sCount[s.charAt(i + pLen) - 'a'] ++;if (Arrays.equals(sCount,pCount)){list.add(i + 1);}}return list;}

三、兩個數組的交集

1、兩個數組的交集(力扣349)

// 1.利用哈希表public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> numsSet = new HashSet<>();Set<Integer> resSet = new HashSet<>();for (int num : nums1){numsSet.add(num);}for (int num : nums2){if (numsSet.contains(num)){resSet.add(num);}}int[] resArray = new int[resSet.size()];int index = 0;for (int i : resSet){resArray[index ++] = i;}return resArray;}

//2.雙指針public static int[] intersection3(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);Set<Integer> set = new HashSet<>();int i = 0;int j = 0;while (i < nums1.length && j < nums2.length) {if (nums1[i] == nums2[j]) {set.add(nums1[i]);i++;j++;} else if (nums1[i] < nums2[j]) {i++;} else if (nums1[i] > nums2[j]) {j++;}}int[] ans = new int[set.size()];int index = 0;for (int value : set) {ans[index++] = value;}return ans;}

//3.二分法public static int[] intersection4(int[] nums1, int[] nums2) {Set<Integer> set = new HashSet<>();Arrays.sort(nums2);for (int target : nums1) {if (binarySearch(nums2, target)) {set.add(target);}}int index = 0;int[] ans = new int[set.size()];for (int value : set) {ans[index++] = value;}return ans;}public static boolean binarySearch(int[] num, int target) {int left = 0;int right = num.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (num[mid] == target) {return true;} else if (num[mid] < target) {left = mid + 1;} else if (num[mid] > target) {right = mid - 1;}}return false;}

2、兩個數組的交集 II(力扣350)

// 1.哈希表
public int[] intersect(int[] nums1, int[] nums2) {if (nums2.length < nums1.length){return intersect(nums2, nums1);}/* 記錄元素及元素出現的次數 */Map<Integer, Integer> numMap = new HashMap<>();for (int num : nums1) {numMap.put(num, numMap.getOrDefault(num, 0) + 1);}/* 記錄重復元素 */List<Integer> resList = new ArrayList<>();for (int num : nums2) {if (numMap.containsKey(num) && numMap.get(num) > 0){resList.add(num);numMap.put(num, numMap.get(num) - 1);}}/* 構建返回數組*/int[] resArray = new int[resList.size()];for (int i = 0; i < resList.size(); i++) {resArray[i] = resList.get(i);}return resArray;}

//2.排序+雙指針 前提：兩個數組是排好序的public int[] intersect(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int i = 0,j = 0;int len1 = nums1.length,len2 = nums2.length;List<Integer> list = new ArrayList<>();while(i < len1 && j < len2){if(nums1[i] == nums2[j]){list.add(nums1[i]);i ++;j ++;}else if(nums1[i] < nums2[j]){i ++;}else{j ++;}}int size = list.size();int[] ans = new int[size];for(int index = 0;index < size; index++){ans[index] = list.get(index);}return ans;}

三、其他的哈希表題

1、快樂數(力扣202)

//1.普通方法//兩種情況：1 最終是1  2. 陷入循環public static boolean isHappy(int n) {Set<Integer> set = new HashSet<>();//如果n不是1，而且沒有陷入循環，就不停迭代while (n != 1 && !set.contains(n)){set.add(n);n = getSum(n);}return n == 1;}
//獲取一個數的各個位上的數字的平方和public static int getSum(int n){int sum = 0;while (n > 0){int num = n % 10;sum += num * num;n /= 10;}return sum;}

//2.快慢指針//兩種情況：如果成環，且不是1，返回falsepublic static boolean isHappy(int n) {int slow = n;int fast = getSum(n);while (fast != 1 && fast != slow){//慢指針每次走一步slow = getSum(fast);//快指針每次走兩步fast = getSum(getSum(slow));}return fast == 1;}

2、兩數之和(力扣1)

	public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> numIndexMap = new HashMap();int[] result = new int[2];for(int i = 0;i < nums.length;i ++){if(numIndexMap.containsKey(target - nums[i])){result[0] = i;result[1] = numIndexMap.get(target - nums[i]);}numIndexMap.put(nums[i], i);}return result;}

3、四數相加 II(力扣454)

//四個數組兩兩組合，等效成兩個數組之和public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int len = nums1.length;Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i < len;i ++){for(int j = 0;j < len; j ++){map.put(nums1[i] + nums2[j],map.getOrDefault(nums1[i] + nums2[j],0) + 1);}}int count = 0;for(int i = 0;i < len;i ++){for(int j = 0;j < len; j ++){if(map.containsKey(-(nums3[i] + nums4[j]))){count += map.get(-(nums3[i] + nums4[j]));}}}return count;}

時間復雜度O(n2),空間復雜度O(n2)

4、三數之和(力扣15)

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> resList = new ArrayList<>();if (nums == null || nums.length < 2){return resList;}Arrays.sort(nums);for (int i = 0; i < nums.length - 2; i++) {/* 最小的數大于0，直接結束 */if (nums[i] > 0){break;}/* 跳過重復值 */if (i > 0 && nums[i] == nums[i - 1]){continue;}int startIndex = i + 1;int endIndex = nums.length - 1;while (startIndex < endIndex){if (nums[startIndex] + nums[endIndex] + nums[i] == 0){resList.add(Arrays.asList(nums[startIndex], nums[endIndex], nums[i]));startIndex ++;endIndex --;while (startIndex < endIndex && nums[startIndex] == nums[startIndex - 1]){startIndex ++;}while (startIndex < endIndex && nums[endIndex] == nums[endIndex + 1]){endIndex --;}} else if (nums[startIndex] + nums[endIndex] + nums[i] < 0){startIndex ++;} else {endIndex --;}}}return resList;}

5、四數之和(力扣18)

public static List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> resList = new ArrayList<>();if (nums.length < 4){return resList;}/* 數組排序 */Arrays.sort(nums);int numLen = nums.length;for (int i = 0; i < numLen - 3; i++) {/* 跳過重復值 */if (i > 0 && nums[i] == nums[i - 1]){continue;}for (int j = i + 1; j < numLen - 2; j++) {/* 跳過重復值 */if (j > i + 1 && nums[j] == nums[j - 1]){continue;}int startIndex = j + 1, endIndex = numLen - 1;while (startIndex < endIndex){long curSum = (long) nums[i] + nums[j] + nums[startIndex] + nums[endIndex];if (curSum == target){resList.add(Arrays.asList(nums[i], nums[j], nums[startIndex], nums[endIndex]));startIndex ++;endIndex --;while (startIndex < endIndex && nums[startIndex] == nums[startIndex - 1]){startIndex ++;}while (startIndex < endIndex && nums[endIndex] == nums[endIndex + 1]){endIndex --;}} else if (curSum < target){startIndex ++;} else {endIndex --;}}}}return resList;}