LeetCode_哈希表

一、哈希表

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;}