当前位置：首页 > article >正文

力扣-Hot100-哈希【算法学习day.30】

article 2024/11/14 9:32:46

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.两数之和

题目链接:1. 两数之和 - 力扣（LeetCode）

题面:

基本分析:每次遍历把该数存到map里，然后每次遍历时看target - nums[i]是否存在于map中，如果存在，则说明找到了

代码:

class Solution {
    public int[] twoSum(int[] nums, int target) {
     int[] ans = new int[2];
     Map<Integer,Integer> map = new HashMap<>();
     int n = nums.length;
     for(int i = 0;i<n;i++){
        int a = nums[i];
        int b = target-nums[i];
        if(map.getOrDefault(b,-1)!=-1){
            ans[0] = i;
            ans[1] = map.get(b);
            break;
        }
        map.put(a,i);
     }
     return ans;
    }
}

2.字母异位词分组

题目链接:49. 字母异位词分组 - 力扣（LeetCode）

题面:

基本分析:字母异位词们将各字符从小到大排序后是一样的单词

代码:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for (String str : strs) {
            char[] s = str.toCharArray();
            Arrays.sort(s);
            // s 相同的字符串分到同一组
            m.computeIfAbsent(new String(s), k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(m.values());
    }
}

3.最长连续序列

题目链接:128. 最长连续序列 - 力扣（LeetCode）

题面:

基本分析:可以通过将每个数存到map里，然后找的时候看相邻的数在map里存不存在，但这样复杂度太高了，我采用指针遍历的线性做法

代码:

class Solution {
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        if(n==0)return 0;
        Arrays.sort(nums);
        int l = 1;
        int count = 1;
        int max = 1;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(nums[0],1);
        while(l<n){
         map.put(nums[l],1);    
        while(l+1<n&&nums[l]==nums[l+1])l++;//防止出现这种类型的排序：0 1 1 2
        if(map.getOrDefault(nums[l]-1,0)!=0){
            count++;
        }else{
            max = Math.max(count,max);
            count = 1;    
        }
        l++;
        }
          max = Math.max(count,max);
        return max;
    }
}