哈希
难度说明：🟢简单🟡中等🔴困难
哈希
🟢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(n2)，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;
}
}