3. 哈希/映射/散列表

1. 哈希/映射/散列表

1.1 两数之和（1）

    public static void main(String[][] args) {
        new Main().twoSum(new int[]{2, 7, 11, 15}, 9)
    }
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numIndexMap = new HashMap<>(nums.length + (nums.length >> 1));
        for (int i = 0; i < nums.length; ++i) {
            if (numIndexMap.containsKey(target - nums[i])) {
                return new int[]{numIndexMap.get(target - nums[i]), i};
            }
            numIndexMap.put(nums[i], i);
        }
        return new int[0];
    }

1.2 字母异位词分组（49）

• 解法一：排序后作为key 使用map来判断重复 O(mnlogn)

    public List<List<String>> groupAnagrams(String[] strs) {
        //判断是否为空字符串数组
        if(strs == null || strs.length == 0){
            return new ArrayList<>();
        }
        //1.创建一个哈希表
        Map<String,List<String>> map = new HashMap<>();
        for (String s: strs) {
            //将字符串转化为字符数组
            char[] chars = s.toCharArray();
            //对字符数组按照字母顺序排序 O(k Log k)
            Arrays.sort(chars);
            //将排序后的字符串作为哈希表中的key值 O(n)
            String key = String.valueOf(chars);
            //2.判读哈希表中是否有该key值
            map.computeIfAbsent(key, temp -> new ArrayList<>()).add(s);
        }
        //返回map中所有键值对象构成的list
        return new ArrayList<>(map.values());
    }

• 解法二：优化Key的获取方式：但是会浪费O(26n)的空间 时间复杂度降低到O(mn)

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        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 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    stringBuilder.append((char) ('a' + i));
                    stringBuilder.append(counts[i]);
                }
            }
            String key = stringBuilder.toString();
            map.computeIfAbsent(key, temp -> new ArrayList<>()).add(key);
        }
        return new ArrayList<List<String>>(map.values());
    }

1.3 有效的字母异位词（242）

• 解法一：利用两个数组统计26个字母的出现频次；比较字符串出现次数即可。 O(n)

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] intArr = new int[26];
        for (int i = 0; i < s.length(); i++) {
            intArr[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            intArr[t.charAt(i) - 'a']--;
            if (intArr[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }