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

哈希

🟢01-两数之和（1）

1.题目内容

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

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

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

2.题解思路

👻方法1：暴力枚举

​ 暴力枚举：迭代数组中的每一个数 x ，看是否存在target - x （嵌套循环数组，外层循环遍历x，内层循环依次判断是否存在 x + y = target，存在则封装返回）。此处需注意的是每个位于x前面的数是在前面的循环中已经和x比较过了，因此对于y的起始是从x+1开始，且需注意数组遍历的临界值处理

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        // 没有匹配到满足的条件
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：O(n²)，n 是数组中的元素数量，最坏情况下数组中的任意两个数都要被匹配1次
• 空间复杂度：O(1)

👻方法2：哈希表

​ 方法1中时间复杂度较高的原因是查找target-x的时间复杂度较高，需要一种优化方法能够快速寻找数组中是否存在元素目标，存在的找出其索引。因此引入哈希表，将寻找target-x的时间复杂度从O(N)降低到O(1)。

​ 外层循环遍历x，然后将x的值作为key，内层判断是否满足hashtable.containsKey(target - x)，存在则直接返回，否则将对应索引 i 作为value存入哈希表

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<len;i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        // 没有匹配到满足的条件
        return new int[0];
    }
}

​ 对比方法1，相当于此处在循环过程中将x摘出来，放到一个HashMap中，然后每次循环都先判断map中是否匹配x + y = target这个条件，匹配则返回，不匹配则继续将x摘出来（保证不会让x和自己匹配），直到所有操作完成

• 时间复杂度：O(n)，n 是数组中的元素数量，对于么一个元素x可以O(1)快速寻找target - x
• 空间复杂度：O(n)，n 是数组中的元素数量，主要为哈希表的开销

3.答题反思（不足之处）

20240814：暴力拆解

（1）基本思路正确，但是需简化代码逻辑结构

（2）每个位于 i 前面的数据是比较过的数据了，所以 j 不需要从头开始，只需要接着 i 后面走即可

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for(int i=0 ;i< nums.length ; i++){
            for(int j=i+1;j< nums.length ; j++){
                if((nums[i] + nums[j]) == target){
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return null;
    }
}

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

1.题目内容

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

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

​ 例如输入["eat","tea","tan","ate","nat","bat"]，输出[["bat"],["tan","nat"],["eat","tea","ate"]]

2.题解思路

​ 关键：抓住字母异位词的概念核心，互为字母异位词的两个字符串包含的字母相同，因此此处可以有两种思路：排序、计数

​ 排序：对两个字符串分别进行排序之后得到的字符串一定是相同的

​ 计数：字符串中的相同字母出现的次数一定是相同的

方法1：排序

核心：定义Map<String,List<String>>，将字符串内部排序作为key，将对应字符串装入这个key对应的value（List 集合中）

• 可以将字符串转化为字符数组，然后使用Arrays.sort工具类对字符数组进行排序
• 对相同字母序列的字符串进行分组使用Map进行存储（key：某个内部排序后的字符串，value 对应的字母异位字符串列表）
• 循环遍历字符串列表，先排序，根据当前key获取到对应的list列表，然后将当前字符串加入到获得的列表中，并更新map内容

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
    	// 定义结果集（存储排序后的字母异位词，和对应的分组）
        Map<String,List<String>> map = new HashMap<>();
        
        for(String str : strs){
            // 将字符串转化为字符数据后排序
            char[] strArr = str.toCharArray();
            // 使用工具类进行数组内部元素排序
            Arrays.sort(strArr);
       		String sortedStr = new String(strArr);
            // 获取当前key对应的list列表
            List<String> list = map.getOrDefault(sortedStr,new ArrayList<String>());// 此处直接获取指定key对应的list，不存在就创建一个新的
            // 将当前字符串加入到对应列表中
            list.add(str);
            // 更新map
            map.put(sortedStr,list);
        }
        // 将map的value值列表转化为ArrayList集合
        return new ArrayList<List<String>>(map.values());
    }
}

复杂度分析

• 时间复杂度：O(nk logk)（n为strs中字符串数量，k为strs中字符串最大长度）
  • 需要遍历n个字符串，对于每个字符串需要O(k logk)时间进行排序以及O(1)的时间更新哈希表，因此总时间复杂度为O(nk logk)
• 空间复杂度：O(nk)
  • 需要用哈希表存储全部字符串

利用Java8的Stream API简化

• 根据排序后字母序列相同的字符串进行分组

return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(s -> Arrays.toString(s.codePoints().sorted().toArray()))).values());

方法2：计数

​ 思路：统计每个字符串中每个字符出现的次数，然后依次比较是否一致，如果都一致认为是字母异位词

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

1.题目内容

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

​ 例如：

• 输入：nums = [100,4,200,1,3,2]；输出：4 （1,2,3,4）
• 输入：nums = [0,3,7,2,5,8,4,6,0,1]；输出：9（1,2,3,4,5,6,7,8,）

2.题解思路

​ 核心：排序、去重后得到一个有序的集合，然后校验当前元素和其下一个元素是否连续，连续则进入下一个判断，如果出现不连续的情况则断掉

​ 注意：需注意去重、排序的处理，避免先排序后又引入无序集合做去重导致"排序失效"

• 先将数组进行去重、排序，获得一个新的集合
  • 如果用的是无序集合，则对Set处理（涉及到一个边界概念）
  • 如果用的是有序集合，则循环遍历校验当前元素和其下一个元素不连续（相差不为1）则说明连续序列断了，当前元素所在的位置就是最长的连续序列**（推荐）**

// 排序、去重（大数组会占用一定的性能消耗），然后遍历统计最长连续序列
public class Solution128 {
    public int longestConsecutive(int[] nums) {
        // 判断nums是否为空
        if(nums==null || nums.length==0){
            return 0;
        }
        // 定义一个新集合，对nums进行去重、排序
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if(!list.contains(num)){
                list.add(num);
            }
        }
        // 连续序列可能从中间才开始，需要一个指针current来进行记录，定义maxLength记录最大值
        int current = 1;
        int maxLength = 1;
        
        // 遍历新集合，依次校验当前元素和其下一个元素是否连续，如果连续则计数+1并更新maxLength，如果断掉则当前current即为当前的连续序列大小，连续序列断掉需要重新计数
        for (int i=0;i<list.size()-1;i++) {
            if( list.get(i+1) - list.get(i) == 1){
               // 满足连续，计数+1
                current ++;
                // 更新当前的maxLength,取大值
                maxLength = Math.max(current,maxLength);
            }else{
                // 连续序列断掉，current又重新计数
                current = 1;
            }
        }
        return maxLength;
    }
}

// 推荐解法：进一步优化：只对数组进行排序而不用额外去重，对于重复元素则直接跳过校验
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length ==0) {
            return 0;
        } else {
            // 排序
            Arrays.sort(nums);
            int maxLength = 1, current = 1;
            // 遍历时跳过重复的元素
            for(int i=1; i<nums.length; i++) {
                if(nums[i] - nums[i-1] ==1) {
                    current++;
                    maxLength = Math.max(maxLength, current);
                } else if(nums[i] == nums[i-1]) {
                    continue;
                } else {
                    current = 1;
                }
            }
            return maxLength;
        }   
    }
}

3.答题反思

• 误区1：误认为"起点一定要从最小的数开始"，但实际上连续序列可能是在中间（例如0,3,4,5，连续序列最长为3）
  • 错误点在于认为启动从最小的数开始，断掉了就跳出循环

public class Solution128 {
    public int longestConsecutive(int[] nums) {
        // 判断nums是否为空
        if(nums==null || nums.length==0){
            return 0;
        }
        // 定义一个新集合，对nums进行去重、排序
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if(!list.contains(num)){
                list.add(num);
            }
        }
        // 遍历新集合，依次校验当前元素和其下一个元素是否连续，如果连续则跳出当次循环继续下一个校验，如果断掉则当前元素位置即为最大连续序列
        // 误区：忽略了连续序列可能从中间才开始，需要一个指针来进行记录
        int maxLength = 1;
        for (int i=0;i<list.size()-1;i++) {
            if( list.get(i+1) - list.get(i) == 1){
               // 满足连续，计数+1
                maxLength ++;
                // 跳出当次循环
                continue;
            }else{
                return maxLength;
            }
        }
        return maxLength;
    }
}