4. 哈希表、映射、集合

1. 题目

https://leetcode-cn.com/problems/valid-anagram/description/
https://leetcode-cn.com/problems/group-anagrams/
https://leetcode-cn.com/problems/two-sum/description/

2. 题解

2.1 有效的字母异位词#242（简单）

public boolean isAnagram(String s, String t) {
    //法一:哈希表。时间复杂度O(n),空间复杂度O(n)
    int sLength = s.length();
    int tLength = t.length();
    if (sLength != tLength) {
        return false;
    }
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < sLength; i++) {
        char c = s.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    for (int i = 0; i < tLength; i++) {
        char c = t.charAt(i);
        map.put(c, map.getOrDefault(c, 0) - 1);
        if (map.get(c) < 0) {
            return false;
        }
    }
    return true;
}
public boolean isAnagram(String s, String t) {
    //法二:先排序再比较。时间复杂度O(nlogn),空间复杂度O(n)
    if (s.length() != t.length()) {
        return false;
    }
    char[] s1 = s.toCharArray();
    char[] t1 = t.toCharArray();
    Arrays.sort(s1);
    Arrays.sort(t1);
    return Arrays.equals(s1, t1);
}
public boolean isAnagram(String s, String t) {
    //法三:哈希表的数组做法。时间复杂度O(n),空间复杂度O(n)
    if (s.length() != t.length()) {
        return false;
    }
    int[] alpha = new int[26];
    for (int i = 0; i < s.length(); i++) {
        alpha[s.charAt(i) - 'a']++;
        alpha[t.charAt(i) - 'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if (alpha[i] != 0) {
            return false;
        }
    }
    return true;
}

2.2 字母异位词分组#49（中等）

https://leetcode-cn.com/problems/group-anagrams/

public List<List<String>> groupAnagrams(String[] strs) {
    //法一:排序存放到哈希表中
    //时间复杂度O(nlogk),k是每个字符串中最大长度,n是字符串个数
    //空间复杂度O(nk),需要把每个字符串都放进map,每个字符串按最大长度k来计算。
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] array = str.toCharArray();
        Arrays.sort(array);
        String key = Arrays.toString(array);
        List<String> list = map.getOrDefault(key, new ArrayList<String>());
        list.add(str);
        map.put(key, list);
    }
    return new ArrayList<List<String>>(map.values());
}


//优秀代码
public List<List<String>> groupAnagrams(String[] strs) {
    return new ArrayList<>(Arrays.stream(strs)
                   .collect(Collectors.groupingBy(str -> {
                       // 返回 str 排序后的结果。
                       // 按排序后的结果来grouping by，算子类似于 sql 里的 group by。
                       char[] array = str.toCharArray();
                       Arrays.sort(array);
                       return new String(array);
                   })).values());
}

public List<List<String>> groupAnagrams(String[] strs) {
    //法二:利用数组计数然后存放到哈希表中
    //时间复杂度O(n(k+m)),k是每个字符串中最大长度,n是字符串个数,m是字符集
    //空间复杂度O(n(k+m)),需要把每个字符串都放进map,每个字符串按最大长度k来计算。
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        int length = str.length();
        int[] counts = new int[26];
        for (int i = 0; i < length; i++) {
            counts[str.charAt(i) - 'a']++;
        }
        //将每个出现次数大于0的字母和出现次数按照顺序拼接成字符串，作为哈希表的key
        StringBuilder sb = new StringBuilder();
        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());
}


//优秀代码
public List<List<String>> groupAnagrams(String[] strs) {
    return new ArrayList<>(Arrays.stream(strs)
       .collect(Collectors.groupingBy(str -> {
           int[] counter = new int[26];
           for (int i = 0; i < str.length(); i++) {
               counter[str.charAt(i) - 'a']++;
           }
           StringBuilder sb = new StringBuilder();
           for (int i = 0; i < 26; i++) {
               // 这里的 if 是可省略的，但是加上if以后，生成的sb更短，后续groupingBy会更快。
               if (counter[i] != 0) {
                   sb.append((char) ('a' + i));
                   sb.append(counter[i]);
               }
           }
           return sb.toString();
       })).values());
}

2.3 两数之和#1（简单）

https://leetcode-cn.com/problems/two-sum/description/

public int[] twoSum(int[] nums, int target) {
    //法一:暴力解法.时间复杂度O(n^2),空间复杂度O(1)
    int length = nums.length;
    for (int i = 0; i < length - 1; i++) {
        int other = target - nums[i];
        for (int j = i + 1; j < length; j++) {
            if (nums[j] == other) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}


public int[] twoSum(int[] nums, int target) {
    //法二:哈希表.时间复杂度O(n),空间复杂度O(n)
    int length = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < length; i++) {
        int another = target - nums[i];
        if (map.containsKey(another)) {
            return new int[]{i, map.get(another)};
        }
        map.put(nums[i], i);
    }
    return null;
}