Leetcode百题斩-哈希

看来面试前还是要老老实实刷leetcode为好，今天看到一个题库，leetcode百题斩，刚好最近面试的这两题全在里面。瞄了一眼，也有不少题之前居然也刷过。那么，冲冲冲，看多久能把这百题刷完。

第一天，先刷第一个专题哈希。感觉作为一个竞赛生，刷这种题应该没什么难度。那就不用C++了，直接上JAVA

1. Two Sum[Easy]

思路：作为leetcode首题，太经典的哈希表了

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> numMap = new HashMap<>();int len = nums.length;for (int i = 0; i < len; i++) {int complement = target - nums[i];if (numMap.containsKey(complement)) {return new int[] {numMap.get(complement), i};}numMap.put(nums[i], i);}return null;}
}

49. Group Anagrams[Mediam]

思路：异位字母分组，直接将字母排序后进行哈希

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> groupMap = new HashMap<>();for (String str : strs) {String sortedStr = sortString(str);groupMap.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);}return new ArrayList<>(groupMap.values());}private String sortString(String s) {char[] stringC = s.toCharArray();Arrays.sort(stringC);return new String(stringC);}
}

128. Longest Consecutive Sequence[Medium]

思路：最长连续序列，第一想法就是直接排序，然后进行统计。复杂度为 。注意特判一下空数组即可

class Solution {public int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0) {return 0;}Arrays.sort(nums);int numLen = nums.length;int curLen = 1;int maxLen = 1;for (int i = 0; i < numLen; i++) {if (i > 0 && nums[i] == nums[i - 1] + 1) {curLen++;if (curLen > maxLen) {maxLen = curLen;}} else if (i == 0 || nums[i] != nums[i - 1]) {curLen = 1;}}return maxLen;}
}

既然这题被分在了哈希专栏里，那么想想是否可以通过哈希的方法将复杂度降到 。那么排序肯定是排不了了，直接将数组维护在哈希集合中，遍历集合元素，针对每段连续序列的头节点（该数的前一个数不在集合中），向后判断该段连续序列长度

class Solution {public int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0) {return 0;}HashSet<Integer> numSet = new HashSet<>();int maxLen = 1;for (int num : nums) {numSet.add(num);}for (int num : numSet) {if (!numSet.contains(num - 1)) {int curlen = 1;while (numSet.contains(num + curlen)) {curlen++;}if (curlen > maxLen) {maxLen = curlen;}}}return maxLen;}
}

不过虽然这个算法将复杂度降下来了，但是最终的耗时其实还不如排序，可见现在的排序优化已经十分到位了。

560. Subarray Sum Equals K[medium]

思路：求数串中和为k的子串。想到子串问题，当然就想到了前缀和。两个前缀和的差值即为一个子串和。因此，哈希表维护一下前缀和及对应数量。由于 ，因此只需要遍历前缀和，寻找哈希表中  对应的数量即可

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> sumMap = new HashMap<>();int count = 0;int sum = 0;sumMap.put(0, 1);for (int num : nums) {sum += num;int need = sum - k;if (sumMap.containsKey(need)) {count += sumMap.get(need);}sumMap.put(sum, sumMap.getOrDefault(sum, 0) + 1);}return count;}
}