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

【LeetCode 面试经典150题】详细题解之哈希表篇

article 2024/12/28 2:26:00

【LeetCode 面试经典150题】详细题解之哈希表篇

1 哈希表的基础
- 1.1 基础概念及实现
- - 1.2.1 哈希表的工作原理
  - 1.2.2 705.设计哈希集合
  - 1.2.3 706.设计哈希映射
- 1.2 HashMap相关
- - 1.2.1 基本操作
  - 1.2.2 遍历
- 1.3 Hashtable
- 1.4 LinkedHashMap
- 1.5 HashSet
- - **1.5.1基本特性**
  - 1.5.2 基本方法
  - 1.5.3 注意事项
2 383.赎金信
- 2.1 思路
- 2.2 代码
3 205.同构字符串
- 3.1 思路
- 3.2 代码
4 290.单词规律
- 4.1 分析
- 4.2 代码
5 242.有效的字母异位词
- 5.1 思路
- 5.2 代码
6 49. 字母异位词分组
- 6.1 思路
- 6.2 代码
7 1.两数之和
- 7.1 思路
- 7.2 代码
8 202.快乐数（需要复习）
- 8.1 思路
- 8.2 代码
9 219.存在重复元素II
- 9.1 思路
- 9.2 代码
10 128.最长连续序列
- 10.1 思路
- 10.2 代码

1 哈希表的基础

12.23 一刷

哈希表是一种基于哈希算法实现的键值对集合，提供了快速的数据插入、删除和查找功能。Java提供了HashMap、Hashtable和LinkedHashMap等实现哈希表的类。以下是Java哈希表的一些基础概念和操作：

1.1 基础概念及实现

1.2.1 哈希表的工作原理

哈希表通过哈希函数将键（Key）映射到哈希表的索引上，然后通过这个索引来访问值（Value）。如果两个键的哈希值相同（哈希冲突），则通过链表或其他方法来解决冲突。

1.2.2 705.设计哈希集合

705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

class MyHashSet {
    /**
    hash函数用于将key映射到数组中
    用链表法来解决哈希冲突，当两个不同的数映射到数组的同一位置时，将该数接到数组位置的链表后面
     */
    //定义hash表的长度为769
    private static final int BASE = 769;
    private LinkedList[] list;
    public MyHashSet() {
        //初始化哈希表
        list = new LinkedList[BASE]; //初始化LinkedList
        for(int i = 0;i<BASE;i++){
            list[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        int h = hash(key);//找到key映射到hash表中的位置
        Iterator<Integer> iter = list[h].iterator();
        while(iter.hasNext()){
            Integer element = iter.next();
            if(element == key){
                return;
            }
        }
        list[h].offerLast(key);
    }
    
    public void remove(int key) {
        int h = hash(key);
        Iterator<Integer> iter = list[h].iterator();
        while(iter.hasNext()){
            Integer element = iter.next();
            if(element == key){
                list[h].remove(element);
                return;
            }
        }
    }
    
    public boolean contains(int key) {
        int h = hash(key);
        Iterator<Integer> iter = list[h].iterator();
        while(iter.hasNext()){
            int element = iter.next();
            if(element == key){
                return true;
            }
        }
        return false;
    }

    private static int hash(int key){
        return key % BASE;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

1.2.3 706.设计哈希映射

706. 设计哈希映射

已解答

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

class MyHashMap {
    /**
    感觉和上一个哈希表的题差不多，根据key映射到哈希表数组中的位置。
    只是此时，哈希表中的每个元素都应该后面还跟着value，不再是Integer了？
     */
    
    //定义一个Pair
    private class Pair{
        private int key;
        private int value;

        public Pair(int key,int value){
            this.key = key;
            this.value = value;
        }

        public int getKey(){
            return key;
        }

        public int getValue(){
            return value;
        }

        public void setValue(int value){
            this.value = value;
        }
    }

    private static final int BASE = 769;
    LinkedList[] list ;
    public MyHashMap() {
        list = new LinkedList[BASE];
        for(int i = 0;i<BASE;i++){
            list[i] = new LinkedList<Pair>();
        }
    }
    
    public void put(int key, int value) {
        int h = hash(key);
        Iterator<Pair> iter = list[h].iterator();
        while(iter.hasNext()){
            Pair pair = iter.next();
            if(pair.getKey()==key){
                pair.setValue(value);
                return;
            }
        }
        list[h].offerLast(new Pair(key,value));
    }
    
    public int get(int key) {
        int h = hash(key);
        Iterator<Pair> iter = list[h].iterator();
        while(iter.hasNext()){
            Pair pair = iter.next();
            if(pair.getKey()==key){
                return pair.getValue();
            }
        }
        return -1;
    }
    
    public void remove(int key) {
        int h = hash(key);
        Iterator<Pair> iter = list[h].iterator();
        while(iter.hasNext()){
            Pair pair = iter.next();
            if(pair.getKey()==key){
                list[h].remove(pair);
                return;
            }
        }
    }

    private int hash(int key){
        return key % BASE;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

1.2 HashMap相关

HashMap是Java中使用最广泛的哈希表实现，它基于Map接口，允许键值对中的键（Key）和值（Value）为null，并且不保证映射的顺序。

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
Integer value = map.get("key1"); // 返回1
map.remove("key2");

1.2.1 基本操作

put(K key, V value)：将指定的值与此映射中的指定键关联。
get(Object key)：返回指定键所映射的值。
remove(Object key)：如果存在一个键的映射关系，则将其从映射中移除。
keySet()：返回映射中包含的键的Set视图。
values()：返回映射中包含的值的Collection视图。
entrySet()：返回映射中包含的键值映射关系的Set视图

1.2.2 遍历

使用 entrySet()

entrySet() 方法返回哈希表中所有键值对的 Set 视图。这个集合中的每个元素都是一个 Map.Entry 对象，其中包含键和值。

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " => " + value);
}

使用 keySet()

keySet() 方法返回哈希表中所有键的 Set 视图。通过这个集合遍历所有的键，然后使用每个键来获取对应的值。

for (String key : map.keySet()) {
    Integer value = map.get(key);
    System.out.println(key + " => " + value);
}

使用 values()

如果你只对值感兴趣，可以使用 values() 方法获取哈希表中所有值的 Collection 视图。

for (Integer value : map.values()) {
    System.out.println(value);
}

使用 forEach 增强型 for 循环（Java 8+）

Java 8 引入了 forEach 方法，它允许使用增强型 for 循环的语法来遍历 Collection。

map.forEach((key, value) -> System.out.println(key + " => " + value));

使用迭代器 Iterator

使用迭代器 Iterator 来遍历哈希表可以避免在遍历时修改集合导致的 ConcurrentModificationException。

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println(entry.getKey() + " => " + entry.getValue());
}

注意事项

当遍历哈希表时，如果需要修改哈希表（增加或删除元素），推荐使用迭代器 Iterator 的 remove 方法，或者在外部使用 removeIf 方法。
entrySet()、keySet() 和 values() 返回的视图反映了哈希表的当前状态，如果哈希表被修改，视图也会相应地变化。
遍历哈希表的时间复杂度是 O(n)，其中 n 是哈希表中的元素数量。

1.3 Hashtable

Hashtable是遗留类，也实现了Map接口，但它是同步的，不允许键或值为null，并且它的性能通常不如HashMap。

Hashtable<String, Integer> htable = new Hashtable<>();
htable.put("key1", 1);
htable.put("key2", 2);
Integer value = htable.get("key1"); // 返回1
htable.remove("key2");

1.4 LinkedHashMap

LinkedHashMap是HashMap的一个子类，它维护了元素的插入顺序或者访问顺序，取决于构造函数的参数。

LinkedHashMap<String, Integer> lmap = new LinkedHashMap<>();
lmap.put("key1", 1);
lmap.put("key2", 2);
Integer value = lmap.get("key1"); // 返回1
lmap.remove("key2");

1.5 HashSet

HashSet 是 Java 中的一个集合类，它实现了 Set 接口，不允许集合中有重复的元素。HashSet 的行为是由 HashMap 实现的，它使用哈希表来存储元素，因此具有很高的添加、删除和搜索效率。以下是 HashSet 的一些基础知识和遍历方法：

1.5.1基本特性

不允许重复：HashSet 不允许存储重复元素。
无序：HashSet 中的元素是无序的，这意味着元素插入和取出的顺序不一定相同。
非线程安全：HashSet 是非线程安全的，如果需要线程安全，可以使用 Collections.synchronizedSet 或 CopyOnWriteArraySet。

1.5.2 基本方法

// 创建
HashSet<String> set = new HashSet<>();
//添加
set.add("element1");
set.add("element2");
//删除
boolean removed = set.remove("element1"); // 返回 true 如果元素被移除，false 如果元素不存在

// 判断元素是否存在
boolean contains = set.contains("element1"); // 返回 true 如果元素存在，false 否则

// 遍历1 
for (String element : set) {
    System.out.println(element);
}

// 遍历2
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

// 遍历3
set.forEach(element -> System.out.println(element));

// 遍历4
set.stream().forEach(System.out::println);

1.5.3 注意事项

HashSet 中的元素顺序不可预测，如果你需要有序的集合，可以考虑使用 TreeSet。
由于 HashSet 依赖于哈希函数，某些情况下可能会遇到哈希冲突，但 Java 的实现已经足够高效，冲突通常不会影响性能。
当遍历或迭代 HashSet 时，如果需要修改集合，应该使用迭代器的 remove 方法，或者在外部使用 removeIf 方法。

2 383.赎金信

383. 赎金信

简单

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

2.1 思路

简单字符可以用长度为26的数组来记录字符出现的次数

    两个哈希表记录ransomNote和magazin两个字符串中，字符出现的次数，之后再一一比较
    由于是简单的字符，所以可以用两个长度为26的数组来记录字符出现的次数

    cnt_r[26]
    cnt_m[26]
    之后遍历cnt_r中的值，判断cnt_r中的每个字符出现的数量是否大于cnt_m中该字符出现的数量。小于则直接返回false

2.2 代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        /**

         */
        int[] cnt_r = new int[26];
        int[] cnt_m = new int[26];

        for(int i = 0;i<ransomNote.length();i++){
            cnt_r[ransomNote.charAt(i)-'a']++;
        }
        for(int i = 0;i<magazine.length();i++){
            cnt_m[magazine.charAt(i)-'a']++;
        }

        for(int i = 0;i<26;i++){
            if(cnt_r[i]>cnt_m[i]){
                return false;
            }
        }
        return true;
    }
}

3 205.同构字符串

205. 同构字符串

简单

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"
输出：true

示例 2：

输入：s = "foo", t = "bar"
输出：false

示例 3：

输入：s = "paper", t = "title"
输出：true

提示：

1 <= s.length <= 5 * 104
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

3.1 思路

第一遍的时候用1个hashmap，这样会存在s->t一对一，t->s多对多的问题

两个HashMap，分别存储s-> t的映射和t-> s的映射

        用一个HashMap存储s中字符到t的映射关系，之后判断即可
        具体而言，对于s和t，假如是同构的，那么s中的所有字符都能映射到t中。
        即map[s[i]] = t[i] 会对所有的i都满足。
        反之，假如不满足上面条件，则说明不同构。

        举例
        s = egg,t = add
        遍历s和t中的每个元素，
        在第一个元素的时候，得出映射关系为 e->a
        第二个元素 g->d
        第三个元素 g->d，成立。

        具体实现则是，维持两个HashMap，分别存储s->t的映射和t->s的映射。
        因为一个的话会存在这种情况。
        s = bacd
        t = baba
        对于s中的字符满足唯一映射，但是对于t中的，比如b会映射到{b,c}不对。
        
        因此，维持两个map，
        s2t中以s字符为键，映射至t的字符为值
        t2s中以t字符为键，映射至s的字符为值
        从左到右遍历两个字符串，更新哈希表。

        出现冲突时（当前下标i对应的s[i]存在映射，但是映射不为t[i]，或者t[i]存在映射，但是映射不为s[i]）
        返回false

3.2 代码

class Solution {
    public boolean isIsomorphic(String s, String t) {
        /**


         */
        int n = s.length();
        Map<Character,Character> maps2t = new HashMap<>();
        Map<Character,Character> mapt2s = new HashMap<>();
        for(int i = 0;i<n;i++){
            char si = s.charAt(i);
            char ti = t.charAt(i);
            //冲突
            if(maps2t.containsKey(si) && maps2t.get(si) != ti){
                return false;
            }
            if(mapt2s.containsKey(ti) && mapt2s.get(ti) != si){
                return false;
            }

            maps2t.put(s.charAt(i),t.charAt(i));
            mapt2s.put(t.charAt(i),s.charAt(i));
        }
        return true;
    }
}

4 290.单词规律

290. 单词规律

简单

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

提示:

1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔

4.1 分析

和205.同构字符串差不多的题。简单题

4.2 代码

class Solution {
    public boolean wordPattern(String pattern, String s) {
        /**
        感觉和上一题一样，都是维护两个map，然后双向映射。
        思路差不多。
         */
        String[] strs = s.split(" ");
        if(strs.length!=pattern.length()){
            return false;
        }
        Map<Character,String> c2strs = new HashMap<>();
        Map<String,Character> strs2c = new HashMap<>();
        for(int i = 0;i<strs.length;i++){
            char c = pattern.charAt(i);
            if(c2strs.containsKey(c) && !c2strs.get(c).equals(strs[i])){
                return false;
            }
            if(strs2c.containsKey(strs[i]) && strs2c.get(strs[i])!=c ){
                return false;
            }
            c2strs.put(c,strs[i]);
            strs2c.put(strs[i],c);
        }
        return true;
    }
}

5 242.有效的字母异位词

242. 有效的字母异位词

简单

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

5.1 思路

分析，不难

        一个cnt数组

        1.将s中所有出现过的字母放入cnt中记录
        2.遍历t，遇见一个t的字母，就在cnt中减去对应的值。假如减之后cnt值<0，则s和t的字符一定不相同。返回false
        
        3.遍历cnt，假如有不为0的数，返回false

5.2 代码

class Solution {
    public boolean isAnagram(String s, String t) {
        /**

         */
        if(s.length()!=t.length()){
            return false;
        }
        int[] cnt = new int[26];
        for(char c: s.toCharArray()){
            cnt[c-'a']++;
        }

        for(char c: t.toCharArray()){
            cnt[c-'a']--;
            if(cnt[c-'a']<0){
                return false;
            }
        }
        return true;
    }
}

6 49. 字母异位词分组

49. 字母异位词分组

中等

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

6.1 思路

重点是用Arrays.sort排序？排序后的字符串作为key

    遍历strs，对strs中的每个str，先使用Arrays.sort排序，
    维持一个<String,List<String>> 的Map，排序后的字符串作为Key，排序前的作为Value
    最后，遍历Map，取出Map中的所有Value放到List结果中

6.2 代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        /**

         */
        Map<String,List<String>> map = new HashMap<>();
        for(String str:strs){
            char[] str_c = str.toCharArray();
            Arrays.sort(str_c);
            String key = new String(str_c);
            List<String> list = map.getOrDefault(key,new ArrayList<String>());
            list.add(str);
            map.put(key,list);
        }
        List<List<String>> res = new ArrayList<>();
        for(Map.Entry<String,List<String>> entry: map.entrySet()){
            res.add(entry.getValue());
        }
        return res;
    }
}

7 1.两数之和

1. 两数之和

简单

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

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

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

7.1 思路

经典题目，但是第一遍只想得起来暴力

暴力枚举遍历
用Map记录数字和他的下标。之后遍历的时候就能通过hashmap知道target-x是否出现过了。


        枚举遍历
        
        要加速的话可以用空间换时间，用一个Map记录每个数字和他的下标。
        之后给原数组排序。然后双指针遍历。

        上面是一个思路。实际上是记录了之后，在遍历的时候能够借助hashmap知道target-x是否出现过。因此时间复杂度能从O（n^2）降到O（1）
        
        // 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[]{};

7.2 代码

class Solution {
    public int[] twoSum(int[] nums, int target) {


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

8 202.快乐数（需要复习）

202. 快乐数

简单

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 231 - 1

8.1 思路

可以用哈希表做，用哈希表记录出现的数字，当出现重复的时候就可以返回了。

如果重复的数字为1，说明是快乐数，否则不为快乐数。

巧妙的是快慢指针判断有环的解法。具体参考下面

    快慢指针
    快指针每次走2步，慢指针每次走1步，二者相等时，即为1个循环周期
    若有环则一定能相遇，若无环也会相遇，但相遇点为1

    想起来了那道判断链表进环点的题。也是快慢指针。相遇后，让一个新的指针从起点开始，以和慢指针一样的速度行动，相遇的节点即为入环点。
    
    但是本题只用判断循环点是否为1即可。

8.2 代码

class Solution {
    public boolean isHappy(int n) {
        /**

         */
        int slow = n,fast = n;
        do{
            slow = bigSquareSum(slow);
            fast = bigSquareSum(fast);
            fast = bigSquareSum(fast);
        }while(slow != fast);
        if(slow==1){
            return true;
        }
        return false;
    }
    int bigSquareSum(int n){
        int sum = 0;
        while(n!=0){
            sum+= (n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
}

9 219.存在重复元素II

219. 存在重复元素 II

已解答

简单

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

9.1 思路

hashmap的应用

    维护一个HashMap,map中是nums中的值->下标的映射
    遍历nums，假如在遍历时发现map中存储过该值，则根据map取出上次出现的下标，计算是否满足i-j<=k,若不满足，则将当前下标更新为j

9.2 代码

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        /**

         */
        
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int num = nums[i];
            if(map.containsKey(num)){
                if(i-map.get(num)<=k){
                    return true;
                }
            }
            map.put(num,i);
        }
        return false;
        
    }
}

10 128.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

10.1 思路

具体如下。重点是

需要找到可能的连续序列 开始的数字，之后往后遍历计算最长连续序列即可。

        利用hash表来存储nums的值，帮助枚举连续的数

        1.先遍历nums，将nums中的值都存在hashset中
        2.遍历hashset，找到每个可能的连续序列开始的数，然后从该数开始往后遍历，计算最长连续序列

10.2 代码

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

         */
        
        Set<Integer> set = new HashSet<>();
        for(Integer num: nums){
            set.add(num);
        }
        int res = 0;
        for(Integer num: set){
            //2.1 判断是不是连续序列最开始的数
            if(set.contains(num-1)){
                continue;
            }
            //2.2 说明是连续序列最开始的数
            int curres = 0;
            while(set.contains(num++)){
                curres++;
            }
            res = Math.max(res,curres);
        }
        return res;
    }
}