【LeetCodehHot100_0x01】

LeetCodeHot100_0x01

1. 两数之和

解题思路： 暴力枚举法、哈希法
【暴力枚举】

class Solution {public int[] twoSum(int[] nums, int target) {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[0];}
}

【哈希法】要找 x + y = targer,则对于每一个x，只需要用哈希判断存不存在 y = targer - x；

class Solution {public int[] twoSum(int[] nums, int target) {// 存储值（键） + 下标Map<Integer,Integer> hs = new HashMap<>();for(int i=0;i<nums.length;i++) {// containsKey 方法用于寻找键是否存在if(hs.containsKey(target-nums[i])) {return new int[]{i,hs.get(target-nums[i])};}// 将当前映射哈希表hs.put(nums[i],i);}return new int[0];}
}

复习： HashMap数据结构、常用方法、使用场景

一、底层数据结构

HashMap 的底层由 数组 + 链表 + 红黑树 组成，核心设计目标是解决哈希冲突并保证高效操作。
数组：默认长度16，长度始终是2的幂次方，每个元素都是一个桶，上面连接着链表或红黑树
链表：解决哈希冲突，使用链地址法（尾插法避免并发场景死循环）
红黑树：链表长度大于8转换，小于6退化。用于优化查询效率：O(n) —> O(logn)

二、常用方法
Map<R,V> hs = new HashMap<R,V>(); // 声明
put(K key, V value)     // 添加键值对
get(K key)                   // 获取值
containsKey(K key)      // 判断键是否存在
keySet()                // 获取所有键的集合
values()                // 获取所有值的集合
entrySet()              // 获取所有键值对
getOrDefault(K key, V defaultValue) // 安全获取值
三、使用场景： 快速插入/查询、统计频率

2. 字母异位词分词

解题思路： 将字符串排序后作为哈希的键，值则为已经符合的字符串列表
【哈希法】关键在于如何对字符串进行排序、如何更新已有的字符串列表

class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 排序后作为哈希的键,值为存储相同的字符串列表Map<String,List<String>> hs = new HashMap<>();for(String str : strs) {// 取出字符串进行排序char[] str_ = str.toCharArray();Arrays.sort(str_);String key = new String(str_);// 取出该键中已有的字符串列表// 这里犯了一个错，这个列表可能是空的，后面会报错，需要用getOrDefault方法安全取值// List<String> str_list = hs.get(key);List<String> str_list = hs.getOrDefault(key,new ArrayList<>());str_list.add(str);hs.put(key,str_list);}List<List<String>> resList = new ArrayList<>(hs.values());return resList;}
}

复习： 对字符串进行排序思路

对字符串内的字符排序（例如将 “cab” 排序为 “abc”）
方法 1：字符数组排序（最常用）

String str = "cab";
char[] chars = str.toCharArray();
Arrays.sort(chars); // 默认升序排序
String sortedStr = new String(chars); // "abc"

方法 2：使用 Java 8 Stream API

String str = "cab";
String sortedStr = str.chars() // 转为 IntStream.sorted() // 对字符的 Unicode 值排序.collect(StringBuilder::new,StringBuilder::appendCodePoint,StringBuilder::append
).toString(); // "abc"

方法 3：转换为列表排序

String str = "cab";
List<Character> charList = new ArrayList<>();
for (char c : str.toCharArray()) {charList.add(c);
}
Collections.sort(charList); // 升序排序
StringBuilder sb = new StringBuilder();
for (Character c : charList) {sb.append(c);
}
String sortedStr = sb.toString(); // "abc"

3. 最长连续序列

解题思路： 用哈希存下来，然后遍历哈希列表，找到最长连续的序列，其长度就是答案
【哈希法】

class Solution {public int longestConsecutive(int[] nums) {// 哈希 ---> Set版去重Set<Integer> hs = new HashSet<>();for(int num : nums) {// 加入哈希hs.add(num);}int res = 0;    // 记录答案for(int num : hs) {// 查看hs中有多少个连续的值if(!hs.contains(num-1)) { // 重新规划起点int currN = num;int currC = 1;// 开始匹配while(hs.contains(currN + 1)) {currN ++;currC ++;}res = Math.max(res,currC);} }return res;}
}

【动态规划法】定义动规：fn[i] : 以第i个元素结尾的最大值，转移存在以下关系：

==1 : fn[i] = fn[i-1] + 1;
==0 : fn[i] = fn[i-1];
order : fn[i] = 1;

class Solution {public int longestConsecutive(int[] nums) {// 排序 + 动态规划//1. 排除边界值if(nums.length == 1) return 1;if(nums.length == 0) return 0;//2. 排序Arrays.sort(nums);//3. 定义动规方程意义(fn[i] 以第i个元素结尾中最大的连续值长度)int []fn = new int[nums.length];//4. 初始化值fn[0] = 1;int res = fn[0];//5. 遍历更新方程for(int i=1;i<nums.length;i++) {if(nums[i] - nums[i-1] == 1) {fn[i] = fn[i-1] + 1; }else if(nums[i] == nums[i-1]) {fn[i] = fn[i-1];}else {fn[i] = 1;}res = Math.max(res,fn[i]);}return res;} 
}

复习： HashSet常用方法

HashSet（基于 HashMap）
特点：无序，插入/查询 O(1)
常用方法：
add(E e)                // 添加元素
remove(Object o)        // 删除元素
contains(Object o)      // 是否包含元素
TreeSet（基于 TreeMap）
特点：元素有序（自然排序或自定义 Comparator），插入/查询 O(log n)
特有方法：
first(), last()         // 最小/最大元素
ceiling(E e), floor(E e) // 类似 TreeMap

4. 移动零

解题思路： 整体向前偏移，在最后补若干零

class Solution {public void moveZeroes(int[] nums) {// 整体偏移int i = 0;  // 记录非零值指针// 将前面变成非零，后面变成0for(int j=0;j<nums.length;j++) {if(nums[j] != 0) nums[i++] = nums[j];}for(int k = i;k<nums.length;k++) {nums[k] = 0;}}
}

5、盛最多水的容器

解题思路： 双指针，不断缩小容器宽度，记录过程中的最优解
【双指针法】：关键：移动策略：哪边短移动哪边。

class Solution {public int maxArea(int[] height) {// 认识：（长 * 宽）Max、木桶效应// 双端指针，靠近过程必然宽会变小，长要扩大才有最优// 移动那边？肯定是短板的一端移动更优int len = height.length;int res = (len-1) * Math.min(height[0] ,height[len-1]);int i=0,j=len-1;while(i<j) {if(height[i] >= height[j]) j--;else i++;int temp = (j-i)*Math.min(height[i],height[j]);res = Math.max(res,temp);}return res;}
}

6、三数之和（不熟）

解题思路： 使用暴力法无法通过，遇到了时间复杂度问题过高。正确的做法因该是用双指针
【暴力法】超出时间限制 308 / 313 个通过的测试用例

首先通过排序将重复项聚集，便于后续去重；接着通过三重循环枚举所有不重复的三元组。

class Solution {public List<List<Integer>> threeSum(int[] nums) {// 排序 + 暴力枚举所有可能List<List<Integer>> reslist = new ArrayList<>();Arrays.sort(nums);for(int i=0;i<nums.length-2;i++) {// 去重1：if(i>0 && nums[i] == nums[i-1])continue;for(int j=i+1;j<nums.length-1;j++) {// 去重2：if(j>i+1 && nums[j] == nums[j-1]) continue;for(int k=j+1;k<nums.length;k++) {// 去重3：if(k >j+1 && nums[k] == nums[k-1]) continue;if(nums[i] + nums[j] + nums[k] == 0) {reslist.add(Arrays.asList(nums[i],nums[j],nums[k]));} }}}return reslist;}
}

【双指针法】

三重循环枚举a+b+c==0，在确定a、b后，c只有唯一的一个值
在确定a后，那么 b + c = -a，也就是说b越大，c越小，两者存在一个关系
于是对于第二重循环和第三重循环，我们可以利用双端指针来寻找在a固定下符合的所有b、c集合

class Solution {public List<List<Integer>> threeSum(int[] nums) {// 排序+ 双指针枚举List<List<Integer>> reslist = new ArrayList<>();Arrays.sort(nums);int n = nums.length;for(int a=0;a<n;a++) {// 去重if(a>0 && nums[a] == nums[a-1]) continue;for(int b=a+1,c=n-1;b<n-1;b++){// 去重if(b > a+1 && nums[b] == nums[b-1])continue;// 枚举符合条件的c(c是从大到小枚举的，界限是直到小于就不符合了)while(c>b && nums[b] + nums[c] > -nums[a])c--;if(c==b)break;  // 找不到if(nums[a] + nums[b] + nums[c] ==0)reslist.add(Arrays.asList(nums[a],nums[b],nums[c]));}}return reslist;}
}

7、接雨水（不会）

求解思路： 提前预处理出当前位置的左边最高高度、右边最高高度，然后与当前位置高度差就是当前位置能够储存水的量。再求和。

class Solution {public int trap(int[] height) {// 这道题目理解完其实不难了，关键你要明白一个问题：i位置的雨水量怎么算？// 取决于（i左边最高 ，i右边最高）min【木桶效应】，记为H// i位置的高度h// i位置能储水 H-h// 所以关键在于如何快速的找到i左边、右边的最高高度---提前预处理出来int n = height.length;if(n==0) return 0;int[] leftMax = new int[n];int[] rightMax = new int[n];leftMax[0] = height[0];rightMax[n-1]=height[n-1];for(int i=1;i<n;i++) {leftMax[i] = Math.max(leftMax[i-1],height[i]);}for(int i=n-2;i>=0;i--){rightMax[i] = Math.max(rightMax[i+1],height[i]);}// 计算每一格可以存水量int res = 0;for(int i=0;i<n;i++) {res += Math.min(leftMax[i],rightMax[i]) - height[i];}return res;}
}

8、无重复字符的最长子串

解题思路： 遍历枚举开头，用哈希表判断过程中符合的最长子串
【哈希法】O(N^2)复杂度，还是不太优美

class Solution {public int lengthOfLongestSubstring(String s) {// 用哈希来判断字符串有没有重复if(s.length() < 2) return s.length();int res = 1;for(int i=0;i<s.length();i++) {//	每次循环都定义一个哈希表，用来判断什么时候出现重复的字符，则该长度终止Map<Character,Boolean> hm = new HashMap<>();hm.put(s.charAt(i),true);int temp = 1;for(int j=i+1;j<s.length();j++) {// 判断是否存在当前键if(hm.containsKey(s.charAt(j))) {break;}else {temp++;hm.put(s.charAt(j),true);}}res = Math.max(res,temp);}return res;}
}

【滑动窗口法】优化思路：假设从k到第rk个元素才发生重复冲突，那么k+1到第rk元素定然没有冲突，我们就可以继续向右扩展，直到出现冲突。重复以往。这个思路的好处是利用公共并不冲突的位置减少了很多判断过程，类似一个滑动的窗口一样。只需要一次遍历就可以得到答案。

class Solution {public int lengthOfLongestSubstring(String s) {int n = s.length();if(n<2)return n;// 滑动窗口Set<Character> hs = new HashSet<>();int j = 0, res = 1; // 定义右指针，初始值为-1for(int i=0;i<n;i++) {// 左边指针右移，跳一个 if(i != 0) {hs.remove(s.charAt(i-1));}// 右移指针直到出现冲突while(j<n && !hs.contains(s.charAt(j))) {hs.add(s.charAt(j));j++;}// 更新答案res = Math.max(res,j-i);}return res;}
}

9、找到字符串中所有字母异位词 (不熟)

解题思路： 这题的解题思路几乎和我想的一样，滑动窗口 + 哈希表维护。需要学习的是它的代码思路，通过Arrays工具类中的equals方法可以快速判断两个数列是否完全相同，真是让我学了一招，这样的话，我们利用数组将字符串p中的字符组成拷贝下来，在维护窗口的过程中，判断更新的s的子串是否也是与p相同的字符组成，是则代表该字符串的开头就是一个答案。

class Solution {public List<Integer> findAnagrams(String s, String p) {// 滑动窗口 + 数组哈希int[] Scnt = new int[26];int[] Pcnt = new int[26];int size = p.length();int n = s.length();if(n < size) return new ArrayList<Integer>();List<Integer> res = new ArrayList<>();for(int i=0;i<size;i++) {Scnt[s.charAt(i)-'a']++;Pcnt[p.charAt(i)-'a']++;}// （不要漏了！！）判断开头是不是原本就符合要求的if(Arrays.equals(Scnt,Pcnt)) {res.add(0);}for(int i=0;i<n-size;i++) { // 枚举当前需要删除的窗口左值Scnt[s.charAt(i)-'a']--;    // 滑动窗口维护左边的字符对应的数量减少Scnt[s.charAt(i+size)-'a']++; // 窗口右侧对应的字符数量增加// 判断字符组成是否完全相同if(Arrays.equals(Scnt,Pcnt)) {res.add(i+1);}}return res;}
}

10、和为K的子数组

求解思路： 暴力两层循环直接过了，不懂
【暴力法】

class Solution {public int subarraySum(int[] nums, int k) {int res = 0;int n = nums.length;// 左边界for(int i=0;i<n;i++) { int sum = nums[i];// 不要漏if(sum == k) {res += 1;// continue;    这个是错误的，虽然已经相等了，但是不能忘记后面可能会有+0的情况}// 右边界for(int j=i+1;j<n;j++) {sum += nums[j];if(sum == k) {res += 1;// break; 这个是错误的，虽然已经相等了，但是后面可能还有 +0 或 正负和为0}}}return res;}
}