LeetCode Hot100 - 哈希篇

时间：2024-10-14 07:10:04

前言

        准备找实习啦，挑战一个月刷完力扣的hot100，记录一下每题的思路~

        这次是哈希相关的题目

（1）1. 两数之和

        ①暴力遍历两遍，找到和为target的两个数

        ②map，每个数先在map中找目的数，若没有才put。因此，若结果为两个相同的数，不会覆盖前一个数，保证不会与自己匹配

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

（2）49. 字母异位词分组

        ①用Array.sort(str)对每个字符串排序，使用map记录sortStr对应的List，更新map时直接取出list，返回值用map.values()

        ②遍历每个字符串的字符，将字符和次数拼接作为key，用map记录list，更新map同上

class Solution {
    Map<String,List<String>> map = new HashMap<>();
    public List<List<String>> groupAnagrams(String[] strs) {
        for(String str:strs){
            int[] counts = new int[26];
            for(char c:str.toCharArray())counts[c-'a']++;//计数
            // 拼接为String作为key
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<26;i++)
                if(counts[i]!=0)sb.append((char)('a'+i)).append(counts[i]);
            String key = sb.toString();
            // 更新map
            List<String> list = map.getOrDefault(key,new ArrayList<>());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList<>(map.values());
    }
}

（3）128. 最长连续序列

        ①排序后遍历，用continue去重。但Array.sort()使用归并排序，时间复杂度n*log(n)

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length<1)return nums.length; // 最多只有一个数
        int res = 1, temp = 1;
        Arrays.sort(nums); // 排序
        for(int i=1;i<nums.length;i++){
            if(nums[i]==nums[i-1])continue; // 重复跳过
            if(nums[i]==nums[i-1]+1)temp++;
            else{ // 更新
                res = Math.max(res,temp);
                temp = 1;
            }
        }
        return Math.max(res,temp);
    }
}

        ②set去重并便于查找，对于每个数，如果set中有其前驱数就跳过，否则一直往后找，记录最长结果

class Solution {
    Set<Integer> set = new HashSet<>();
    public int longestConsecutive(int[] nums) {
        for(int i:nums)set.add(i); // 去重，便于查找
        int res = 0;
        for(int num:set){
            if(set.contains(num-1))continue; // 存在前驱数，跳过
            int tempNum=num, temp=1;
            while(set.contains(tempNum+1)){ // 一直往后找
                temp++;
                tempNum++;
            } 
            res=Math.max(res,temp);
        }
        return res;
    }
}

总结

        ①哈希有map和set，map常用于键值对映射，set常用于去重和存在性查找

        ②两数之和，用map寻找target-num[i]是否存在，注意先判断再put，保证不会匹配到自身

        ③字母异位词分组，用map键值对映射进行分组，可以使用str的排序作为key，也可以将字符和次数统计为字符串作为key

        ④最长连续序列，用set去重并查找，并跳过存在前驱数的情况

相关文章