难度说明：🟢简单🟡中等🔴困难

hot150-05-哈希表

🟢01-赎金信（383）

1.题目内容

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

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

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

2.题解思路

👻方法1：比较+剔除

• 思路分析：循环对比判断ransomNote 的每个字符是否出现在magazine 中，如果没有出现则说明不满足，如果出现则剔除后进入下一个字符的判断

/**
 * 383 赎金信
 */
public class Solution1 {

    /**
     * ransomNote 中的字符可否由magazine中的字符构成（magazine中的字符只能使用一次）
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        // 将magazine中的字符存入哈希表中
        List<Character> list = new ArrayList<>(magazine.length());
        for(int i=0;i<magazine.length();i++){
            list.add(magazine.charAt(i));
        }

        // 校验ransomNote中的字符是否可由magazine构成
        for(int i = 0;i<ransomNote.length();i++){
            // 如果不包含则返回false
            if(!list.contains(ransomNote.charAt(i))){
                return false;
            }
            // 移除已经使用过的元素
            int idx = list.indexOf(ransomNote.charAt(i));
            list.remove(idx);
        }

        return true;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

​ 上述操作思路可以直接在原字符串上进行操作，不需要额外引入空间比较

/**
 * 383 赎金信
 */
public class Solution2 {

    /**
     * ransomNote 中的字符可否由magazine中的字符构成（magazine中的字符只能使用一次）
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        // 校验ransomNote中的字符是否可由magazine构成
        for(int i = 0;i<ransomNote.length();i++){
            String findTarget = ransomNote.charAt(i) + "";
            // 如果不包含则返回false
            if(!magazine.contains(findTarget)){
                return false;
            }
            // 移除已经使用过的元素
            magazine = magazine.replaceFirst(findTarget,"");
        }
        return true;
    }
}

👻方法2：排序+指针比较法

• 思路分析：
  • （1）分别对两个字符串数据进行排序
  • （2）依次比较两个字符串内容，如果ransomNote的指针可以遍历到尾部则说明符合

/**
 * 383 赎金信
 */
public class Solution3 {

    /**
     * ransomNote 中的字符可否由magazine中的字符构成（magazine中的字符只能使用一次）
     * 排序+指针比较法
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        // 对两个字符串内容进行排序
        char[] ransomNoteArr = ransomNote.toCharArray();
        char[] magazineArr = magazine.toCharArray();
        Arrays.sort(ransomNoteArr);
        Arrays.sort(magazineArr);

        // 依次遍历数组元素，如果ransomNote可以走完全程则说明匹配
        int rp = 0,mp = 0; // rp 表示ransomNote遍历指针，mp表示magazine遍历指针
        while(rp<ransomNoteArr.length && mp<magazineArr.length){
            if(ransomNoteArr[rp]==magazineArr[mp]){
                // 匹配，则两个指针继续向前
                rp++;
                mp++;
            }else{
                // 不匹配，则寻找下一个满足的mp位置
                mp++;
            }
        }

        // 遍历完成（当两个字符串其中一个走到尾部，说明遍历结束）
        return rp==ransomNoteArr.length;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟢02-同构字符串（205）

1.题目内容

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

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

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

示例 1:

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

示例 2：

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

示例 3：

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

2.题解思路

👻方法1：规律法

​ 基于同构字符串的解释，实际上可以理解为：判断两个字符串中每个字符出现的位置是否相等

​ 获取当前元素所在的第一个 index 是否一样，如果不一样，则说明一定有某一个元素映射此处超过 1 次。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        for(int i = 0; i < s.length(); i++){
            if(s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))){
                return false;
            }
        }
        return true;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

👻方法2：映射法（🟢）

• 思路分析：

  • 构建一个映射集合存储s->t的字符映射：Map<a,b> 其中key为 s 对应遍历元素，value为 t 对应遍历元素
  • 如果映射表中：key包括a，则说明存在a字符的映射关系，需进一步判断其value是否和当前的b匹配
    • 如果对应映射关系不和b字符匹配则直接返回false
  • 如果映射表中：key不包括a，则需要根据value中是否包括b进一步判断
    • value不包括b，则可以直接构建一组映射
    • value包括b，则说明当前b此前被其他元素映射过，但是该值却不是当前的a，因此返回false

  /**
   * 205 同构字符串
   */
  public class Solution2 {
  
      /**
       * 定义一个Map存储S->T对应的映射集
       */
      public boolean isIsomorphic(String s, String t) {
          // 定义哈希表存储S->T的映射集合（key为s对应字符，value为其在T的对应映射字符）
          Map<Character, Character> map = new HashMap<>();
          // 遍历元素，构建映射集并进判断
          for (int i = 0; i < s.length(); i++) {
              char curS = s.charAt(i);
              char curT = t.charAt(i);
              // 如果map中key中包括a，则说明映射存在，需进一步校验t对应位置的值是否和value匹配
              if(map.containsKey(curS)){
                  // 判断映射是否匹配
                  if(curT!=map.get(curS)){
                      return false;
                  }
              }else{
                  // 如果map中key不包括curS，则拆分情况讨论，则进一步判断curT是否存在于value中
                  if(map.containsValue(curT)){
                      // 如果存在，则说明curT字符已有映射关系存在，且该映射关系并不是curS，因此直接返回false
                      return false;
                  }else{
                      // 如果不存在，则说明可以构建一组映射关系
                      map.put(curS,curT);
                  }
              }
          }
          return true;
      }
  }
  

• 复杂度分析

  • 时间复杂度：O（n）最坏的情况是遍历完所有的元素，一次单层遍历

  • 空间复杂度：O（n）需要借助哈希表构建映射关系记录，n为字符串大小长度

🟢03-单词规律（290）

1.题目内容

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

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

2.题解思路

👻方法1：映射法（🟢）

​ 此题的题解思路可以和上述同构字符串有异曲同工之妙，只不过此处不是字符和字符的映射，而是字符和字符串的映射，且需注意字符的个数和切割后的字符串个数必须一致才有下一步比较的必要

/**
 * 290 单词规律
 */
public class Solution1 {

    /**
     * 映射法：通过构建字符和对应字符串的映射进行匹配
     * Map<key,value>:key存储字符，value存储字符对应映射的字符串
     * 遍历pattern每个字符c，判断其的映射关系是否满足双向连接的规律
     * 1.如果map中的key包括c：说明存在c相关的映射关系，则进一步校验对应映射的字符串是否匹配
     * 2.如果map中的key不包括c：则根据value进一步校验
     * - 如果map中的value不包括str（当前校验的字符串），则可以构建一组新的映射关系
     * - 如果map中的value包括str（当前校验的字符串），则说明当前字符串str已经存在一组映射关系，且其并不为c（即不满足双向连接）
     */
    public boolean wordPattern(String pattern, String s) {

        // 定义哈希表存储字符和字符串的映射关系
        Map<Character,String> map = new HashMap<>();

        // 对字符串元素进行切割
        String[] strs = s.split("\\s+");

        // 如果长度不匹配则无需进一步校验
        if(pattern.length()!=strs.length){
            return false;
        }

        // 遍历pattern每个字符，校验是否满足双向连接匹配规则
        for(int i=0;i<pattern.length();i++){
            // 判断map中的key是包含当前字符
            char cur = pattern.charAt(i);
            if(map.containsKey(cur)){
                // 进一步校验value是否匹配
                if(!strs[i].equals(map.get(cur))){
                    return false;
                }
            }else {
                // 判断map的value中是否包括当前要校验的字符串
                if(map.containsValue(strs[i])){
                    return false; // 存在则说明当前字符串已经有映射关系了，且这个映射关系对照的字符并不是cur
                }else{
                    map.put(cur,strs[i]); // 不存在，则可构建一组新的映射关系
                }
            }
        }

        return true;
    }

}

• 复杂度分析

  • 时间复杂度：O（n）遍历一遍元素

  • 空间复杂度：O（n）需要一个map存储映射关系，需要一个String[] 存储切割字符串列表信息

同理，类似的也有比较索引，判断元素第一次出现位置

class Solution {
    public boolean wordPattern(String pattern, String s) {
        List<String> ls = Arrays.asList(s.split(" "));
        int n = pattern.length();
        if (n != ls.size()) return false;
        for (int i = 0; i < n; i++) {
            if (pattern.indexOf(pattern.charAt(i)) != ls.indexOf(ls.get(i)))
                return false;
        }
        return true;
    }
}

🟢04-有效的字母异位词（242）

1.题目内容

​ 给定两个字符串 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 仅包含小写字母

2.题解思路

​ 字母异位词：每个单词的出现次数一样

• 统计法：统计两个字符串中每个单词出现次数，然后依次进行比较，确认是否完全一致
• 比较剔除法：如果两个单词长度不一致则肯定不满足要求，如果长度一致则遍历其中一个字符串（例如s）的每个字符，判断其是否在t中存在，存在则剔除，不存在则不满足条件。直到元素遍历完成，此时t如果也恰好为空，则说明满足字母异位词的条件
• 排序法：字母异位词排序后的序列完全一致，因此可以对排序后的序列进行一一匹配

👻方法1：计数法

/**
 * 242 有效的字母异位词
 */
public class Solution1 {
    public boolean isAnagram(String s, String t) {

        // 如果两个字符串长度不一致，则没有继续比较的必要(直接不满足)
        if(s.length()!=t.length()){
            return false;
        }

        // 统计法，统计每个元素出现的次数是否一致
        Map<Character,Integer> sMap = new HashMap<>();
        Map<Character,Integer> tMap = new HashMap<>();

        // 遍历元素，统计字符出现次数
        for(int i=0;i<s.length();i++){
            // 统计s中字符出现次数
            char sCh = s.charAt(i);
            sMap.put(sCh,sMap.getOrDefault(sCh,0)+1);
            // 统计s中字符出现次数
            char tCh = t.charAt(i);
            tMap.put(tCh,tMap.getOrDefault(tCh,0)+1);
        }

        // 遍历统计的内容，确认是否一致
        if(sMap.size()!=tMap.size()){
            return false;
        }
        Set<Character> keys = sMap.keySet();
        for (Character key : keys) {
            if(sMap.get(key)!=tMap.get(key)){
                return false;
            }
        }

        return true;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

👻方法2：比较剔除法

public class Solution2 {
    public boolean isAnagram(String s, String t) {
        // 如果两个字符串长度不一致，则没有继续比较的必要(直接不满足)
        if (s.length() != t.length()) {
            return false;
        }

        // 遍历元素，比较剔除
        for(int i=0;i<s.length();i++){
            t = t.replaceFirst(s.charAt(i) + "","");
        }

        // 如果最终t中的所有元素被移除，则说明满足字母异位词条件
        return t.length()==0;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

👻方法3：排序法

public class Solution3 {
    public boolean isAnagram(String s, String t) {

        // 如果两个字符串长度不一致，则没有继续比较的必要(直接不满足)
        if(s.length()!=t.length()){
            return false;
        }

        // 将字符串转字符数组
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();

        // 对元素进行排序
        Arrays.sort(sArr);
        Arrays.sort(tArr);

        // 遍历元素，确认是否一一匹配
        for(int i=0;i<sArr.length;i++){
            if(sArr[i]!=tArr[i]){
                return false;
            }
        }

        return true;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟡05-字母异位词分组（49）

1.题目内容

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

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

示例 1:

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

示例 2:

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

示例 3:

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

2.题解思路

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

• 计数法：字符序列中所有字符出现次数对应一致
• 排序法：字符序列排序后的内容一致
• 比较剔除法：判断长度是否一致，遍历某个字符串s中的字符，如果对应字符在另一个字符串t中出现则移除，直到所有元素遍历完成，最终如果s与t是字母异位词的话，则s与t最终的结果应该是完全匹配的，即s遍历完成且t字符串中相应元素一一被移除

👻方法1：排序法

• 思路分析
  • 字母异位词排序后的字符序列是完全一致的，因此可以采用排序的思路进行分组，借助Map存储分组信息
    • Map<k,v>：k 存储排序后的字母异位词信息（校验分组规则），v 存储同属于字母异位词语的字符串列表

/**
 * 049 字母异位词分组
 */
public class Solution1 {
    /**
     * 排序法：排序后的字母异位词序列是完全一致的
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        // 定义结果
        Map<String,List<String>> map = new HashMap<>(); // key 字母异位词排序后的序列，value对应匹配的字符串

        // 遍历数组元素进行依次校验
        for(int i=0;i<strs.length;i++){
            // 获取校验源字符数组并进行排序
            char[] targetArr = strs[i].toCharArray();
            Arrays.sort(targetArr); // 排序
            String key = new String(targetArr);
            // 获取对应字母异位词映射，如果不存在则存入
            List<String> targetList = map.getOrDefault(key,new ArrayList<>());
            targetList.add(strs[i]); // 更新对应分组信息
            map.put(key,targetList); // 更新map
        }

        // 返回响应结果
        /*
        List<List<String>> res= new ArrayList<>();
        map.forEach((k,v)->{res.add(v);});
        return res;
        */
        return new ArrayList<List<String>>(map.values()); // 上述语句可以不需要遍历封装，直接调用方法封装
    }
}

• 复杂度分析

  • 时间复杂度：O(n k logk)。需要遍历n个元素进行校验，对于每个字符串需要O(k logk)的时间进行排序以及O(1)时间更新哈希表

  • 空间复杂度：O(nk)，n是strs中字符串的数量，k是strs中字符串的最大长度(需要用哈希表存储字符串)

👻方法2：计数法

• 思路分析
  • 可以自定义方法对字母序列进行计数，此处计数有两个小技巧（不需要用map存储每个字符出现字数然后进行匹配），而是借助题意（字符串全部都是小写字母），说明字符串中的字符构成已经确定下来，因此只需要定义一个数组count[]分别用于存储26个字母的出现次数，然后将统计后的结果组合成字符串作为key进行校验
    • count[]：用于存储每个字母出现的次数（count[]：（count[0]存储的是a出现次数，count[b]存储的是b出现次数，以此类推））
      • 下标和字符转化：'a'-'a' = 0 即 （str.charAt(i) - 'a'可以将字符串对应i位置的字符转为相应的下标索引）
    • 例如Map<k,v>：k 为字符出现次数统计序列（例如a3b6c0d16....这种形式），然后只需要根据这个key来进行分组匹配即可

/**
 * 049 字母异位词分组
 */
public class Solution2 {
    /**
     * 计数法：
     * count[] 形式：存储每个字母出现的次数（count[0]存储的是a出现次数，count[b]存储的是b出现次数，以此类推）
     * Map<k,v>：k 字符出现次数统计结果序列，v对应分组的字母异位词列表
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        // 定义结果
        Map<String,List<String>> map = new HashMap<>(); // key 字符出现次数统计结果序列，value对应匹配的字符串

        // 遍历字符串数据，分别进行统计
        for(String str : strs){
            int count[] = new int[26];
            for(int i=0;i<str.length();i++){
                count[str.charAt(i) - 'a'] ++; // 将字母转化为对应的数字进行存储：`a`对应0，`b`对应1等
            }

            // 统计完成将统计序列组合成key进行存储
            StringBuffer key = new StringBuffer();
            for(int i=0;i<26;i++){
                key.append('a'+i).append(count[i]);
            }

            // 根据key更新字母异位词列表
            List<String> targetList = map.getOrDefault(key.toString(),new ArrayList<>());
            targetList.add(str);
            map.put(key.toString(),targetList);
        }

        // 返回结果
        return new ArrayList<>(map.values());

    }
}

🟢06-两数之和（01）

1.题目内容

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

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

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

2.题解思路

👻方法1：暴力法（❌）

• 思路分析：双层循环进行遍历，外层循环遍历nums元素，内层循环找满足（a+b=target）的元素（已经校验过得元素可以不需要再校验，因此此处内层循环起点是在i+1位置）

/**
 * 001 两数之和
 */
public class Solution1 {
    // 暴力法
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{};
    }
}

• 复杂度分析

  • 时间复杂度：O(n²) n 为数组长度，双层循环嵌套遍历

  • 空间复杂度：O(1)

👻方法2：哈希表

• 思路分析：引入哈希表进行元素存储，提升检索效率

/**
 * 001 两数之和
 */
public class Solution2 {
    // 哈希表
    public int[] twoSum(int[] nums, int target) {
        // 定义哈希表存储元素（key：元素 value：元素对应下标索引）
        Map<Integer,Integer> map = new HashMap<>();

        // 遍历元素，依次加入元素并校验
        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 new int[]{};
    }
}

• 复杂度分析

  • 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，可以 O(1) 地寻找 target - x

  • 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销

🟢07-快乐数（202）

1.题目内容

编写一个算法来判断一个数 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

2.题解思路

👻方法1：哈希表

• 思路分析：借助哈希集合检测循环

  • 思路：根据当前值，判断其下一个会变成的数，并校验是否属于快乐数
  • 下一个会变成的数：是根据当前的n决定的（其是通过每个位置上数字的平方和来获取）
    • 例如7=>49=>16+81=97=>81+49=>130=>1+9+0=>10=>1+0=>1
  • 判断其是否为快乐数，即判断其结果是否为1。从上述分析，如果说这个过程中已经存在一个已经计算过的数，那么就会陷入循环，永远无法到达终点
    • 例如116=>1+1+36=38=>9+64=73=>49+9=58=>25+64=89=>64+81=145=>1+16+25=42=>16+4=20=>4+0=4=>16=>1+36=37=>9+49=58=>25+64=89 .....,可以看到如果后面计算的数字在前面已经出现过，则整个计算会进入循环，因此这种情况是不会出现快乐数的

• 算法实现：

  • getNext：定义方法根据当前值计算器下一个数（即对其进行数位分离得到平方和）
  • validHappy：校验快乐数（通过set存储已经计算过的数字），如果出现循环的情况则说明其不是快乐数

/**
 * 202 快乐数
 */
public class Solution1 {

    /**
     * 快乐数校验：
     * 判断 n 通过数位分离、计算平方和之后能否得到1，这个过程中如果出现循环则永远不可能到达1
     */
    public boolean isHappy(int n) {
        // 定义一个哈希集合，存储已经计算过的数字，如果出现非1的循环数字则说明其非快乐数，否则一直往下找，直到找到结果为1
        HashSet<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) {
            set.add(n); // 将已经计算的元素加入集合
            n = getNext(n); // 获取下一个值
        }
        return n == 1;
    }

    // 根据n获取下一个值（数位分离、计算平方和）
    public int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10; // 取余（每次取最尾部的数字进行分离计算）
            sum += d * d;
            n = n / 10; // 去除尾部继续计算
        }
        return sum;
    }
}

• 复杂度分析

  • 时间复杂度：O（logn）

  • 空间复杂度：O（logn）引入了哈希表存储

👻方法2：数学规律法（❌）

• 思路分析：根据题意分析可以得到相应的循环规律：4, 16, 37, 58, 89, 145, 42, 20
  • 可以看到，实际上这种思路是通过观察数学规律的思路穷举这些循环规律，如果说计算得到的下一个值在这个循环数的集合里面，那么就无法满足快乐数的条件，但此前提是需要将这些循环数都给找出来，这个过程还是需要分析的，一般不会采用这种类似分析数学规律穷举的思路，偏向暴力解法

class Solution {

    private static Set<Integer> cycleMembers =
        new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));

    public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }


    public boolean isHappy(int n) {
        while (n != 1 && !cycleMembers.contains(n)) {
            n = getNext(n);
        }
        return n == 1;
    }
}

• 复杂度分析

  • 时间复杂度：O（logn）

  • 空间复杂度：O（1）

🟢08-存在重复元素II（219）

1.题目内容

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

2.题解思路

👻方法1：暴力法（❌超时）

• 思路分析（和【两数之和】的思路类似，循环遍历数据元素，外层找i内层找j，判断条件是否满足）

public class Solution1 {
    // 暴力法：双层循环嵌套，判断是否满足条件
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                // 判断是否符合条件
                if (nums[i] == nums[j] && Math.abs(i - j) <= k) {
                    return true;
                }
            }
        }
        // 没有找到，返回false
        return false;
    }
}

• 复杂度分析

  • 时间复杂度：O（n）

  • 空间复杂度：O（1）

👻方法2：哈希表（🟢）

• 思路分析（和【两数之和】的思路类似，循环遍历数据元素，判断是否存在匹配条件的数据，将元素依次加入集合）
  • 定义map存储数组元素和其对应下标索引
  • 循环遍历数组元素，判断是否存在匹配条件的数据，将元素依次加入集合中
  • 此处的设定在于是先校验后加入元素如果在过程中发现满足条件的数据则可直接返回true

public class Solution2 {

    // 哈希表
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        // 构建哈希表存储元素及其对应数组下标索引
        Map<Integer, Integer> map = new HashMap<>();

        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 判断是否符合匹配的条件
            if (map.containsKey(nums[i]) && Math.abs(i - map.get(nums[i])) <= k) {
                return true;
            }
            // 将元素加入集合
            map.put(nums[i], i);
        }
        // 没有找到，返回false
        return false;
    }
}

• 复杂度分析

  • 时间复杂度：O（n）需要遍历一次数组，对于每个元素哈希表的操作时间是O（1）

  • 空间复杂度：O（n） 消耗空间为哈希表存储空间，n 为数组长度

3.复盘

🟡09-最长连续序列（128）

1.题目内容

给定一个未排序的整数数组 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

2.题解思路

👻方法1：暴力法（去重、排序 + 校验连续序列）❌超时

• 思路分析
  • 去重、排序：先对集合进行处理，去重、排序，获取到新的集合
  • 检验连续序列：遍历处理后的集合（检验一些边界的条件），一个有序集合中可能存在多个连续序列，因此在遍历过程中需要记录每个可能的连续序列的最大值
    • 连续序列：当next-prev==1满足则说明是连续的
      • 如果满足连续：记录curLen（当前连续序列的长度），max 最大连续序列的长度
      • 如果不满足则说明当前连续序列断开，需重新开始计数（curLen从1开始，元素本身就是一个连续序列）

/**
 * 128 最长连续序列
 */
public class Solution1 {

    /**
     * 排序、去重、遍历寻找最长前缀
     */
    public int longestConsecutive(int[] nums) {
        // 定义最大序列长度
        int max = Integer.MIN_VALUE;

        // 对数组元素进行去重、排序
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if (list.contains(num)) {
                continue;
            }
            list.add(num);
        }

        // 对处理后的列表进行特殊情况讨论
        if (list.size() <= 1) {
            return list.size();
        }

        /**
         * 遍历处理好的元素，寻找最长的连续序列
         * 1.连续序列相邻两个值之间间隔为1
         * 2.连续序列可以从中间任意节点开始
         * - 集合中可能存在多个连续序列，每个连续序列断开的点是下一个连续序列开始的点
         * - 元素本身就是一个连续序列，因此curLen从1开始计数
         */
        int curLen = 1; // 记录以当前指定元素为起点的连续序列长度
        // 计算以每个元素为起点能得到的最大连续序列，记录max
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i + 1) - list.get(i) == 1) {
                curLen++;
                max = Math.max(max, curLen);
            } else {
                curLen = 1; // 连续序列断掉，需重新计数
            }
        }

        // 返回结果
        return max == Integer.MIN_VALUE ? 1 : max; // 元素本身是一个序列
    }
}

• 复杂度分析

  • 时间复杂度：O（n）需对数组元素进行排序、循环遍历元素

• 空间复杂度：O（n）主要用于存储哈希表元素

👻方法2：哈希表（去重+校验）

​ 哈希表的思路引入了哈希表进行检索优化，不需要额外的排序工作。其核心思路在于：寻找连续序列的开头（即其前1个数不存在，则其为连续序列的开头，就算只有1个，它本身也是一个连续序列），当找到开头元素则进一步进入循环检索其递增序列的长度（每次递增1，直到序列断开）

• 思路分析：
  • （1）对数组元素进行去重，加入set集合
  • （2）遍历去重后的set集合元素，校验每个连续序列，以100 4 200 1 3 2为例分析
    • 目的：寻找连续序列的开头（例如100...），如果是开头则只需要对这个开头的数字进行内层循环遍历，直到这个序列不再连续
    • 100：集合中不存在99（说明100是开头），判断以100开头的连续序列的长度，只有100因此这个连续序列长度为1
    • 4：集合中存在3（说明4不是开头），跳过
    • 200：集合中不存在199（说明200是开头），判断以200开头的连续序列的长度，只有200因此这个连续序列长度为1
    • 1：集合中不存在0（说明1是开头），判断以1开头的连续序列的长度1 2 3 4，到4断开了，因此这个连续序列长度为4
    • 3：集合中存在2（说明3不是开头），跳过
    • 2：集合中存在1（说明2不是开头），跳过
    • 最终得到连续序列为分别以100、200、1开头的序列，其中最长的连续序列长度为4

/**
 * 128 最长连续序列
 */
public class Solution2 {

    /**
     * 去重+哈希表：
     * （1）先对数组元素进行去重，引入哈希表HashSet存储
     * （2）遍历set，寻找每个连续序列的开头（如果某个元素的前一个数不存在，则其可以作为连续序列的开头）
     * - 找到开头元素，进一步进入内存循环遍历获取到连续序列（依次递增判断，直到序列断开）
     */
    public int longestConsecutive(int[] nums) {
        int max = Integer.MIN_VALUE;
        // 去重
        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }

        if(set.isEmpty()){
            return 0;
        }

        /**
         * 遍历元素：寻找开头元素，并敲定以开头元素为起点的连续序列长度
         */
        for(int num : nums){
            // 判断是否为开头元素（当前num的前一个数不存在，则其可作为连续序列的开头元素），如果非开头元素则可忽略
            if(!set.contains(num-1)){
                // 计算当前轮次的连续序列长度
                int curLen = 1; // 起始值为1（元素本身也是一个连续序列）
                int curNum = num; // 当前连续序列起始点

                // 进入内层循环进行校验，直到连续序列断掉
                while(set.contains(curNum+1)){
                    // 集合中存在下一个值，则更新连续序列长度
                    curLen++;
                    curNum++; // 指向下一个位置
                }
                // 更新最大的连续序列长度
                max = Math.max(max,curLen);
            }
        }

        // 返回结果
        return max==Integer.MIN_VALUE?1:max;
    }
}

• 复杂度分析

  • 时间复杂度：O（n） n为数组长度

  • 空间复杂度：O（n） 哈希表存储数组中所有的数