《LeetCode热题100》---＜哈希三道＞

本篇博客讲解

LeetCode热题100道中的哈希篇中的三道题。分别是

1.第一道：两数之和（简单）

2.第二道：字母异位词分组（中等）

3.第三道：最长连续序列（中等）

第一道：两数之和（简单）

class Solution {public int[] twoSum(int[] nums, int target) {int left = 0,right = nums.length-1;Arrays.sort(nums);while (left < right){if(nums[left] + nums[right] < target) {left++;}else if(nums[left] + nums[right] > target){right--;}else {return new int[]{left,right};}}return new int[]{left,right};}
}

方法一：暴力枚举

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[0];}
}

我们通过双循环。遍历数组中每一个两数之和。若和等于target。

此时我们返回数组两个数的数组下标。这样的思想很简单，不过效率不高。

方法二：哈希表

注：

java的官方文档建议我们在初始化哈希表的时候尽量写入哈希表的容量，避免哈希表扩容所带来的性能消耗。

class Solution {public int[] twoSum(int[] nums, int target) {int len = nums.length;Map<Integer, Integer> hashTable = new HashMap<Integer, Integer>(len-1);hashTable.put(nums[0],0);//向哈希表存入数组第一个数//从第二个数开始遍历数组，看哈希表中是否存在target减去此时数组的数所对应的值//如果有，则返回下标。//没有则将这个数放进哈希表。并存入数组下标。for (int i = 1; i < len; ++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];}
}

我们通过Map类创建一个哈希表。

1.向哈希表存入数组第一个数
2.从第二个数开始遍历数组，看哈希表中是否存在target减去此时数组的数所对应的值
3.如果有，则返回下标。
4.没有则将这个数放进哈希表。并存入数组下标。

---

 第二道：字母异位词分组（中等）

方法一：哈希+排序 

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<String, List<String>>();for (String str : strs) {char[] array = str.toCharArray();Arrays.sort(array);String key = new String(array);List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key, list);}return new ArrayList<List<String>>(map.values());}
}

 遍历其中的字符串。将他们转换为数组方便操作。对于每个单词。进行排序。 作为哈希表的键。将单词加入哈希表。返回的就是答案。

方法二：哈希+计数

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<String, List<String>>();for (String str : strs) {int[] counts = new int[26];int length = str.length();for (int i = 0; i < length; i++) {counts[str.charAt(i) - 'a']++;}// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键StringBuffer sb = new StringBuffer();for (int i = 0; i < 26; i++) {if (counts[i] != 0) {sb.append((char) ('a' + i));sb.append(counts[i]);}}String key = sb.toString();List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key, list);}return new ArrayList<List<String>>(map.values());}
}

将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键。

第三道：最长连续序列（中等）

暴力的方法是 O(n) 遍历数组去看是否存在这个数，我们就不多说了，这里我们来看更高效的哈希表法。

哈希表

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<Integer>();for (int num : nums) {set.add(num);}int longestStreak = 0;for (int num : set) {if (!set.contains(num - 1)) {int currentNum = num;int currentStreak = 1;while (set.contains(currentNum + 1)) {currentNum += 1;currentStreak += 1;}longestStreak = Math.max(longestStreak, currentStreak);}}return longestStreak;}
}

1.首先定义一个Set类去重，并将去重后的数组放入Set中

2.初始化最长连续序列longestStreak令其为0。

3.遍历Set。去找是否存在num-1。这个数。

如果不存在，则记录当前的num为currentNum。且令currentStreak为1。并且循环在set中查找是否包含currentNum。如果包含就一直更新currentStreak的值，直到不包含为止。并每次取得currentStreak与longestStreak的最大值赋值给longestStreak

如果存在则跳过。

最终返回longestStreak