LeetCode HOT100（一）哈希

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解法1：暴力枚举

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];
}

解法2：HashMap
在从前往后遍历的过程中，使用HashMap保存遍历过的值，如果后续有节点和前面的值能配对，则可以直接从Map中取出。

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0; i<nums.length; i++){
        if(map.containsKey(target-nums[i])){
            res[1] = i;
            res[0] = map.get(target-nums[i]);
            return res;
        }else{
            map.put(nums[i],i);
        }
    }
    return res;
}

func twoSum(nums []int, target int) []int {
    res := make([]int,0)
    m := make(map[int]int,10)
    for i,v := range nums{
        _,exist := m[target-v];
        if exist {
            res = append(res,i,m[target-v]) 
            return res
        }else{
            m[v] = i
        }
    }
    return res
}

字母异位词分组

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

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

解法1：存Map

• 用 Map<String,List> 来保存每一种异位词
• 遍历所有词，首先对词进行排序
• 判断 Map 是否存在这个异位词
  • 是，则向其 value 的链表添加这个词
  • 否，新建一个 list 作为这个 key 的 value，将当前这个词添加进去

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> res = new ArrayList<>();
    Map<String,List<String>> map = new HashMap<>();
    for(int i=0; i<strs.length; i++){
        String cur = strs[i];
        char[] c = cur.toCharArray();
        Arrays.sort(c);
        //不能tostring
        String key = String.valueOf(c);
        if(map.containsKey(key)){
            map.get(key).add(cur);
        }else{
            List<String> tmp = new ArrayList<>();
            tmp.add(cur);
            map.put(key,tmp);
        }
    }
    for(Map.Entry<String,List<String>> entry:map.entrySet()){
        res.add(entry.getValue());
    }
    return res;
}

解法2：计数（推荐，时间复杂度更低，但力扣时间更高）
不对每个字符串排序，而是遍历字符串，记录每个字符串出现的次数，最后通过a1b2这种拼接好的26个字母的个数作为key存到map中

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> res = new ArrayList<>();
    Map<String,List<String>> map = new HashMap<>();
    for(int i=0; i<strs.length; i++){
        String cur = strs[i];
        int[] count = new int[26];
        for(int j=0; j<cur.length(); j++){
            count[cur.charAt(j)-'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for(int j=0; j<26; j++){
            sb.append('a'+j);
            sb.append(count[j]);
        }
        String key = sb.toString();
        List<String> list = map.getOrDefault(key,new ArrayList<>());
        list.add(cur);
        map.put(key,list);
    }
    for(Map.Entry<String,List<String>> entry:map.entrySet()){
        res.add(entry.getValue());
    }
    return res;
}

func groupAnagrams(strs []string) [][]string {
    m := make(map[string][]string,len(strs))
    for _,str := range strs{
        key := sort(str)
        m[key] = append(m[key],str)
    }
    res := make([][]string,0,len(m))
    for _,v := range m{
        res = append(res,v)
    }
    return res;
}

func sort(str string) (res string){
    count := [26]int{}
    for i:=0; i<len(str); i++ {
        count[str[i]-'a']++
    }
    for i,v := range count{
        res = res+string('a'+i)+string(v)
    }
    return res
}

最长连续序列

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

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

解法1：set存储+遍历

• 首先遍历一遍数组，将其放在 Set 中，主要是用来去重，因为重复的元素没意义
• 第二次遍历数组，找连续的序列。要从一个连续序列的起始节点找，所以首先判断当前 Set 中是否存在当前元素的上一个元素
  • 存在，说明当前结点不是第一个，所以直接跳过
  • 不存在，说明当前结点是第一个，开始计算

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for(int i:nums){
        set.add(i);
    }
    int res = 0;

    for(int i:nums){

        if(!set.contains(i-1)){
            int count = 1;
            int num = i;
            while(set.contains(num+1)){
                count+=1;
                num+=1;
            }
            res = res>count?res:count;
        }

    }
    return res;
}

解法2：排序（不满足此题的On要求）

解法3：并查集
https://leetcode.cn/problems/longest-consecutive-sequence/solutions/1453487/by-lfool-jdy4

class Solution {
    public int longestConsecutive(int[] nums) {

        Map<Integer, Integer> map = new HashMap<>();
        UF uf = new UF(nums.length);

        for (int i = 0; i < nums.length; i++) {
            // 存在重复元素，跳过
            if (map.containsKey(nums[i])) continue;

            if (map.containsKey(nums[i] - 1)) {
                uf.union(i, map.get(nums[i] - 1));
            }
            if (map.containsKey(nums[i] + 1)) {
                uf.union(i, map.get(nums[i] + 1));
            }
            map.put(nums[i], i);        
        }
        return uf.getMaxConnectSize();
    }
}
class UF {
    private int[] parent;
    private int[] size;

    public UF(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        parent[rootP] = rootQ;
        // 注意 别写反了
        size[rootQ] += size[rootP];
    }
    // get root id
    private int find(int x) {
        // 路径压缩
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    public int getMaxConnectSize() {
        int maxSize = 0;
        for (int i = 0; i < parent.length; i++) {
            if (i == parent[i]) {
                maxSize = Math.max(maxSize, size[i]);
            }
        }
        return maxSize;
    }
}