哈希表算法学习

什么是哈希表？可以是数组，可以是HashSet，可以是HashMap，我做哈希表这类题时更多的是不知道怎么灵活使用哈希表提供的方法，希望通过这个专题的学习能够有所进步。

HashMap常用方法：

1. put(key，value)，我们经常用存储一些常用的数据，比如flag、百分比之类的，我们就可以返回map结构，如果key相同则值会覆盖，允许key和value为null。
2. get(key)，getOrDefault(key，defaultValue)，主要用来取map中存储的数据，我们根据其key值，可以取到对应的value值，没有该key对应的值则返回null，后者则可以避免空指针异常。
3. remove(key)，主要用来删除map中对应的key及其value值。
4. clear()，会清空map中的数据。
5. containsKey(key)，判断map集合中是否包含某个key。
6. containsValue(value)，判断map集合中是否包含某个value。
7. entrySet()：key和value存储在entry对象里面，遍历的时候，拿到entry对象就可以取到value了，使用例：for (Map.Entry<Character, Integer> entry : map.entrySet())
8. map.values()：可以用于对Map的类型转换，比如return ArrayList<List> (res.values());在处理结果时能方便很多。

HashSet常用方法：

1. add(Object obj)：向Set集合中添加元素，添加成功返回true，否则返回false。
2. size()：返回Set集合中的元素个数。
3. remove(Object obj)： 删除Set集合中的元素，删除成功返回true，否则返回false。
4. isEmpty()：如果Set不包含元素，则返回 true ，否则返回false。
5. clear()： 移除此Set中的所有元素。
6. contains(Object o)：如果Set包含指定的元素，则返回 true，否则返回false。
7. resSet.stream().mapToInt(x -> x).toArray();将Set转化为数组。

数组

有效的字母异位词

问题：给定两个字符串s和t，s和t仅包含小写字母，编写一个函数来判断t是否是s的字母异位词，其实也就是统计两个字符串中出现的所有字母其个数分别是否一样。

字符串仅包含a-z这26个小写字母，通过数组我们可以人为构建哈希映射，即声明一个长度为26的数组，一个字母每出现一次，便在对应数组元素+1，若数组元素完全相同，这两个字符串当然就是字母异位词了。

代码示例：

/**
 * 有效的字母异位词 字典解法
 * 时间复杂度O(m+n) 空间复杂度O(1)
 */
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];

        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;     // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
        }

        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        
        for (int count: record) {
            if (count != 0) {               // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        return true;                        // record数组所有元素都为零0，说明字符串s和t是字母异位词
    }
}

HashSet

两个数组的交集

问题：给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的，可以不考虑输出结果的顺序。

这个问题题目若是给定了nums1和nums2的范围，使用数组当然也是可以的，方法同上，只是多了一步处理最终数据的过程，即将哈希数组中不为0的项的索引加入到另一个数组中。

另一个方法就是使用HashSet集合，HashSet保有Set的性质，即元素不重复，很适合本题背景。诸如这里将HashSet转换为数组的方法运用不是很自如，如果到时候做题不会的话可以考虑第二种写法，就单纯把元素一个一个取出来存在新申请的数组里。

代码示例：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
      
        //方法1：将结果集合转为数组

        return resSet.stream().mapToInt(x -> x).toArray();
        
        //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }
        
        return arr;
    }
}

快乐数

问题：编写一个算法来判断一个数n是不是快乐数，即每一次将该数替换为它每个位置上的数字的平方和，重复这个过程直到这个数变为1，如果这个过程结果为1，那么这个数就是快乐数，无限循环但始终变不到1，则不是快乐数。

看起来比较复杂的一题，实际上利用HashSet的特性即可解决，只要平方和出现重复的，就可以判断其不是快乐数从而结束循环了。

代码示例：

class Solution {

    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<Integer>();
        while(!set.contains(n)){
            set.add(n);
            n = getSum(n);
            if(n == 1)
                return true;
        }
        return false;
    }

    public int getSum(int num){
        int sum = 0;
        while(num > 0){
            sum += (num % 10) * (num % 10);
            num /= 10;
        }
        return sum;
    }
}

最长连续序列

问题：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度，请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

一看到要找相邻元素是否存在，自然想到的就是哈希了。一开始我的想法是先把所有数字加入到HashSet中，遍历数组在Set中查找是否有当前元素-1的元素存在Set当中，发现会有重复的问题，加上判断其实就解决了。

代码示例：

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

无重复字符的最长子串

问题：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

滑动窗口+HashSet，维护HashSet保证不重复，若重复，左窗口滑动直至不再重复，比较简单。

代码示例:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0)
            return 0;
        int left = 0;
        int right = 0;
        int res = 0;
        Set<Character> set = new HashSet<>();
        while(right<s.length()) {        
            if(!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                res = Math.max(res, right - left + 1);
                right++;
            }
            else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return res;
    }
}

HashMap

四数相加II

问题：给定四个包含整数的数组列表A,B,C,D,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0，所有的 A, B, C, D 具有相同的长度 N。

乍一看很像三数之和、四数之和这两道题。实际上四个独立数组要比单独一个数组好处理，对于三数之和，其实两层循环就能确定a + b，理论上来讲c只需要再遍历一遍就能确定，但这样会出现重复的情况，实际情况要复杂的多，而这道题则不需要关注那么多。

这道题主要还是暴露出我对哈希法的应用不太熟练，潜在的有将AB、CD分为两组的意识，但最后却受困于AB索引也可以不同的情况。本题使用HashMap，首先遍历A和B元素，将其和以及和出现的次数存在HashMap中，之后再遍历CD，检查0-C-D是否有元素出现在HashMap中，统计命中次数。

代码示例：

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}

字母异位词分组

问题：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

在上面判断字母异位词的基础上，我们要将若干单词以此进行分组。初次做这道题卡在该如何知道当前单词应该加在哪个之后呢，发现这正是哈希的功能所在，这题主要就是要构建一个独一无二的key能够分辨不同的字母异位词。

我们可以对字符串转换为数组进行排序，也可以用数组做哈希记录每个单词出现的次数并拼接为字符串作为key，后面就没有什么难点了，最后学习一下Map转换为List的方法。

代码示例：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> res = new HashMap<>();
        for(String s : strs) {
            char[] ch = s.toCharArray();
            int[] keyMap = new int[26];
            for(char c : ch) {
                keyMap[c - 'a'] += 1;
            }
            StringBuffer sb = new StringBuffer();
            for(int i = 0; i < 26; i++) {
                if(keyMap[i] != 0)
                    sb.append((char) 'a' + i).append(keyMap[i]);
            }
            String key = sb.toString();
            List<String> list = res.getOrDefault(key, new ArrayList<String>());
            list.add(s);
            res.put(key, list);
        }
        return new ArrayList<List<String>> (res.values());
    }
}

找到字符串中所有的字母异位词

问题：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

这题也是字母异位词相关的题目，解决方式一般都是维护异位词的HashMap，遍历到搜索串的字符如果存在于HashMap中并且剩余量不为0，计算长度+1并将Map中对应字母的Value-1，记录当前长度，若是长度为字母异位词长度就说明找到了一个字母异位词。同样的对于26个字母可以用数组做哈希，但是思想和上面所述是一致的。

代码示例：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.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)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

最小覆盖子串

问题：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

这题其实跟异位词相关的题目很像，不过这次是子串只要包含就行，依然是哈希+滑动窗口，首先明确最小的子串左右边界上的字符一定是属于t的，接下来思路其实很简单，也就是t的哈希中还没被全部包含，右窗口就往右移动，同时不断维护哈希，若是右移到刚好包含全部t中元素，就记录此时的left和right和长度便于最终返回答案，超出哈希中元素的个数就需要左窗口向右移动收缩窗口。

本题需要学习的就是如何高效维护哈希和窗口，详见代码。这里给出的方法只维护遍历s的哈希，不对t的哈希再做修改，我觉得确实很值得学习，首先是对右指针遍历到的元素的处理，不管元素是什么先加入s，这实际上也比较符合正常思考的逻辑，若是当前元素属于t并且个数小于等于t，就对记录包含t中元素的个数的count加1。接着的循环负责的是处理窗口的收缩，当出现s.charAt(right)) > mapT.get(s.charAt(right))的时候，左指针就会右移，直至

代码示例：

class Solution {
    public String minWindow(String s, String t) {

        int left = 0;
        int right = 0;
        String res = new String();
        int count = 0;
        int length = Integer.MAX_VALUE;
        Map<Character, Integer> mapS = new HashMap<>();
        Map<Character, Integer> mapT = new HashMap<>();
        for(int i = 0; i < t.length(); i++) {
            mapT.put(t.charAt(i), mapT.getOrDefault(t.charAt(i), 0)+1);
        }

        while(right < s.length()) {
            mapS.put(s.charAt(right), mapS.getOrDefault(s.charAt(right), 0) + 1);
            if(mapT.containsKey(s.charAt(right)) && mapS.get(s.charAt(right)) <= mapT.get(s.charAt(right)))
                count++;
            while(left < right && (!mapT.containsKey(s.charAt(left)) || mapS.get(s.charAt(left)) > mapT.get(s.charAt(left)))) {
                mapS.put(s.charAt(left), mapS.get(s.charAt(left)) - 1);
                left++;
            }
            if(count == t.length() && right - left + 1 < length) {
                length = right - left + 1;
                res = s.substring(left, right + 1);
            }
            right++;
        }
        return res;

    }
}

和为K的子数组

问题：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

这题一开始想用排序+滑动窗口去做，后来发现不能改变这个数组原本的顺序，那么就只好做哈希去找了，但是直接对元素做哈希并不好解决问题，考虑前缀和，任何一个子数组的和都可以是末元素结尾前缀和 - 首元素前一个元素结尾前缀和，对前缀和做哈希，遍历数组下标，查找是否存在k + 当前前缀和的元素在哈希中。

需要注意的是，这里要避免重复的问题，解决的办法就是遍历时再将前缀和加入哈希表中。

代码示例：

class Solution {
    public int subarraySum(int[] nums, int k) {

        int[] preSum = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            if(i > 0) 
                preSum[i] = nums[i] + preSum[i-1];
            else
                preSum[i] = nums[i];
        }

        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for(int i = preSum.length - 1; i >= 0; i--) {
            map.put(preSum[i], map.getOrDefault(preSum[i], 0) + 1);
            if(preSum[i] == k)
                res++;
            if(preSum[i] == k + preSum[i] && map.containsKey(k + preSum[i]))
                res += (map.get(k + preSum[i]) - 1);
            if(preSum[i] != k + preSum[i] && map.containsKey(k + preSum[i]))
                res += (map.get(k + preSum[i]));
        }
        return res;
    }
}