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]核心思想： 用哈希表（Map）存储已经遍历过的数字及其下标。对于当前数 nums[i]，检查 target - nums[i] 是否在表中，若存在则直接返回对应下标；否则将当前数存入表。一次遍历即可完成，时间复杂度 O(n)。
题解：
这里使用map，通过将key设置为数组中的值，value设置为位置，在key上可以直接判断是否存在两个数是否可以为target的加数
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> hashmap = new HashMap<>();
for(int i = 0;i < nums.length; i++){
if(hashmap.containsKey(target - nums[i])){
return new int[]{hashmap.get(target - nums[i]),i};
}
hashmap.put(nums[i],i);
}
return new int[]{};
}
}2.字母异位词
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
在 strs 中没有字符串可以通过重新排列来形成
"bat"。字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
核心思想： 字母异位词的特点是：排序后的字符串相同。因此，对每个字符串排序得到 key，用 HashMap 将 key 映射到一组原字符串列表，最后返回所有 value 即可。
题解：
字母异位词，代表元素的值一样只是顺序不一样，那么我们将字符串拆成字符排序，丢到map里面，排序后字符做key，原本字符做值即可
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str : strs){
//转为字符数组做排序
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
//将原来字符串做值
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key,list);
}
//结果返回map的所有值即可
return new ArrayList<List<String>>(map.values());
}
}3.最长序列
给定一个未排序的整数数组 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示例 3：
输入：nums = [1,0,1,2]
输出：3核心思想： 用 HashSet 去重。只对每个可能成为序列起点的数（即 num-1 不在 set 中）进行向后扩展，统计连续长度。这样每个元素最多被访问两次，时间复杂度 O(n)。
题解：
O（n）复杂度无法使用排序
首先使用set将重复元素排除在外，不用考虑遍历到相同值的情况，将值全部加入到set后做遍历判断，
第一层if首先判断当前set是否存在当前元素的上一位的情况，如果存在则不做处理，因为我们需要判断最长序列，拿中间值做计算没有意义，当不存在时，我们默认当前值为序列最小值，向上做判断，如果存在则currentNum,cureentStreak自增，定义longest用来存放最大结果
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num:nums){
set.add(num);
}
int longest = 0;
for(int num:set){
if(!set.contains(num - 1)){
int currentNum = num;
int currentStreak = 1;
while(set.contains(currentNum + 1)){
currentNum++;
currentStreak++;
}
longest = Math.max(longest,currentStreak);
}
}
return longest;
}
}4.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums = [0]
输出: [0]题解：
这题使用双指针来解决移动要保证非零元素的相对顺序，定义左右两指针l,r都从0开始，保证指针r的值始终为0，指针l始终为非0即可。
此处双指针停止条件应为右指针到数组边界，因为需要遍历数组全部元素才可以确定所有值都得到判断和移动；
class Solution {
public void moveZeroes(int[] nums) {
int l = 0,r = 0,n = nums.length;
while(r < nums.length){
if(nums[r] != 0){
swap(nums,l,r);
l++;
r++;
}
else{
r++;
}
}
}
public void swap(int nums[],int l,int r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
}5.成最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1]
输出：1题解：
使用双指针，首先我们从宽度最大情况开始计算，即l = 0,r = height.length - 1， 从宽度最大开始计算面积，逐步缩小宽度，计算每次的面积取最大值即可，注意由于木桶效应，对于两个边界l,r我们只能取最小的高度来计算面积，且左右指针谁的高度小移动谁，因为我们要求最大值。
class Solution {
public int maxArea(int[] height) {
int l = 0,r = height.length - 1;
int ans = 0;
while(l < r){
int area = (r - l ) * Math.min(height[l],height[r]);
ans = Math.max(ans,area);
if(height[l] <= height[r]){
l++;
}
else{
r--;
}
}
return ans;
}
}6.三数之合
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。题解：
这题主要点将求三值为0转为求for循环下i索引值的相反数
这题通过双指针，首先将数组排序，然后将左指针l = 0，右指针 = nums.length - 1,那么左指针则是小值，右指针式大值，通过不断判断左右指针的值之合与目标值是否相等，来获取题解，如果当前值之和小于目标值，则左值指针移动，因为左指针移动成递增，右指针则递减，通过判断与目标值大小关系决定移动哪个指针；由因为题目要不重复的三元数组，所以在获取到target值的时候，做两个while循环判断当前指针值是否与上一个值相等。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for(int i =0;i< nums.length;i++){
int l = i + 1,r = nums.length - 1;
if(i > 0 && nums[i] == nums[i - 1]) continue; // 因为不能重复，所以i自己要做去重处理
int target = -nums[i];
while(l < r){
if(nums[l] + nums[r] == target){
ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
l++;
r--;
while(l < r && nums[l] == nums[l - 1])l++; // 因为不能重复，所以l自己要做去重处理
while(l < r && nums[r] == nums[r + 1])r--; // 因为不能重复，所以r自己要做去重处理
}
else if(nums[l] + nums[r] < target){
l++;
}
else{
r--;
}
}
}
return ans;
}
}给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
7.接雨水
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2：
输入：height = [4,2,0,3,2,5]
输出：9题解：
这题稍微有些复杂，主要是如何将雨水计算抽象；
对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。，由于这题只需要全部的值所以我们将值加起来即可；
这下问题就具象为，找出i值两边的最大值，然后再从最大值里面取最小值，最后与i处高度相减即可；
雨水量 = min(leftMax, rightMax) - height[left]，在if中只处理leftmax < rightmax的逻辑，而当leftMax >= rithtmax 则走else分支，
在看官方题解时，他给出来当height[left] < height[right]，则必有 leftMax < rightMax 这样其实不是数学表述而是计算机逻辑表述，如果把他看成数学范畴的表述，则这里完全不成立；
因为要找出i的左右两边，所以这题使用双指针
class Solution {
public int trap(int[] height) {
int l = 0,r = height.length -1;
int lmax = 0,rmax = 0;
int ans = 0;
while(l <r){
lmax = Math.max(lmax,height[l]);
rmax = Math.max(rmax,height[r]);
if(height[l] < height[r]){
ans += lmax - height[l];
l++;
}
else{
ans += rmax - height[r];
r--;
}
}
return ans;
}
}滑动窗口
核心思想
用两个指针（左、右）围成一个「窗口」，不断移动窗口左右边界，只遍历一遍数组，快速找满足条件的子数组 / 子串，时间复杂度 O (n)。
两个指针
右指针 right：不断向右扩，纳入元素
左指针 left：条件超标时，向右缩，剔除元素
窗口：
[left, right]
三、两大类型
1. 固定窗口（长度不变）
窗口大小固定，一直往右滑
用途：定长求和、定长最大值、定长平均值
例子：长度为 3 的子数组最大和
2. 可变窗口（最常用）
窗口大小自由伸缩，求最长 / 最短满足条件区间
用途：
无重复最长子串
和≥target 最短子数组
包含所有字符最短子串
四、通用流程
初始化
left=0，遍历right把
nums[right]加入窗口窗口不合法：不断移动
left缩小窗口合法时更新答案
right 继续右移
五、最简单例子
求数组中和大于 8 的最短子数组
[2,3,1,2,4,3]右扩累加，和超 8 就缩左
最终得出最短长度 = 2
六、适用场景
数组 / 字符串连续区间问题
求最长、最短、恰好满足条件子段
去重、频次统计、区间求和
七、口诀
右指针猛冲，左指针慢收，一遍走完，快慢双滑
8. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。题解：
这题主要通过滑动窗口来实现，
我们创建一个set来做滑动窗口，计算每一次窗口的长度，然后跟当前值ans比较，取最大值即为题解
窗口存储i处开始的子串
public int lengthOfLongestSubstring(String s) {
Set<Character> occ = new HashSet<>(); // 存储当前窗口内的字符
int n = s.length();
int rk = -1; // 右指针，初始为 -1（表示还没开始）
int ans = 0; // 最长子串长度
for(int i = 0; i < n; i++) {
// i 是左指针
// 1. 如果不是第一次循环，移除左指针前一个字符
if(i != 0) {
occ.remove(s.charAt(i - 1));
}
// 2. 尽可能向右移动右指针
while(rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
occ.add(s.charAt(rk + 1));
++rk;
}
// 3. 更新答案（当前窗口长度 = rk - i + 1）
ans = Math.max(ans, rk - i + 1);
}
return ans;
}执行过程可视化（s = "abcabcbb"）
初始状态
text
i = 0 (左指针)
rk = -1 (右指针，指向窗口最后一个字符)
occ = {} (空集合)第一轮循环 (i = 0)
text
1. i == 0，不删除任何字符
2. while 循环扩展右指针：
- rk+1=0，字符 'a'，occ 不含 'a' → 添加 'a'，rk=0
- rk+1=1，字符 'b'，occ 不含 'b' → 添加 'b'，rk=1
- rk+1=2，字符 'c'，occ 不含 'c' → 添加 'c'，rk=2
- rk+1=3，字符 'a'，occ 包含 'a' → 停止
3. 窗口：[a,b,c]，长度 = 2-0+1 = 3
ans = max(0, 3) = 3状态：
text
字符串: a b c a b c b b
索引: 0 1 2 3 4 5 6 7
窗口: [--------]
左指针: ↑
右指针: ↑
occ = {a, b, c}第二轮循环 (i = 1)
text
1. i != 0，删除左指针前一个字符 s[0] = 'a'
occ = {b, c}
2. while 循环尝试扩展右指针（当前 rk=2）：
- rk+1=3，字符 'a'，occ 不含 'a' → 添加 'a'，rk=3
- rk+1=4，字符 'b'，occ 包含 'b' → 停止
3. 窗口：[b,c,a]，长度 = 3-1+1 = 3
ans = max(3, 3) = 3状态：
text
字符串: a b c a b c b b
索引: 0 1 2 3 4 5 6 7
窗口: [--------]
左指针: ↑
右指针: ↑
occ = {b, c, a}第三轮循环 (i = 2)
text
1. 删除左指针前一个字符 s[1] = 'b'
occ = {c, a}
2. while 循环：
- rk=3，检查 rk+1=4，字符 'b'，occ 不含 'b' → 添加 'b'，rk=4
- rk+1=5，字符 'c'，occ 包含 'c' → 停止
3. 窗口：[c,a,b]，长度 = 4-2+1 = 3
ans 保持 3第四轮循环 (i = 3)
text
1. 删除左指针前一个字符 s[2] = 'c'
occ = {a, b}
2. while 循环：
- rk=4，检查 rk+1=5，字符 'c'，occ 不含 'c' → 添加 'c'，rk=5
- rk+1=6，字符 'b'，occ 包含 'b' → 停止
3. 窗口：[a,b,c]，长度 = 5-3+1 = 3
ans 保持 39.找到字符串中所有的字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。题解：
这里使用字符数组来验证异位词，只需判断字符出现次数不用管排序；
这里使用滑动窗口来判断，
第一次for循环构建s,从索引0开始的窗口，窗口长度时p字符串的长度，在这次循环里可以理解为构建了p字符串的位图，后续我们截取s对应长度的字母位图，跟p的位图作比较，即可判断
当构建完成后，如果两个字符数组内容完全一样，则说明符合题目要求
后续for循环，就从索引1开始，所以在for循环前将i处字符减掉
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int slen = s.length(), plen = p.length();
if(slen < plen){
return new ArrayList<Integer>();
}
int[] sCount = new int[26];
int[] pCount = new int[26];
List<Integer> ans = new ArrayList();
//初始化字符数组，和窗口
for(int i = 0;i< plen; ++i){
++sCount[s.charAt(i) - 'a'];
++pCount[p.charAt(i) - 'a'];
}
if(Arrays.equals(sCount,pCount)){
ans.add(0);
}
for(int i = 0;i< slen - plen;i++){
--sCount[s.charAt(i) - 'a'];
++sCount[s.charAt(i + plen) - 'a'];
if(Arrays.equals(sCount,pCount)){
ans.add(i+1);
}
}
return ans;
}
}10.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2示例 2：
输入：nums = [1,2,3], k = 3
输出：2题解：
使用前缀和，不要把前缀和当成一个数来看，将他抽象为存了前几个元素的数组可能更好理解，
如果存在一个之前的前缀和等于 sum - k，那么从那个前缀和的下一个位置到当前位置的这一段子数组的和一定等于 k。
nums[j] + nums[j+1] + ... + nums[i] = sum[i] - sum[j-1]sum[i] - sum[j-1] = k -》 sum[j-1] = sum[i] - k下列代码，sum表前缀和，
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0);
//保存当前前缀和
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}11.滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7示例 2：
输入：nums = [1], k = 1
输出：[1]题解：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0 || k <= 0){
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
//使用双端队列来维护索引值
Deque<Integer> deque = new ArrayDeque();
for(int i = 0;i < n;i++){
//做窗口滑动，将左侧索引删除
while(!deque.isEmpty() && deque.peekFirst() < i - k + 1){
deque.pollFirst();
}
//当队列里面索引对应值比当前值小，则可以删掉因为求最大值，维护单调递减
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
deque.pollLast();
}
//这里i指的是窗口的右边界，每次入队做记录也可以表左边界
deque.offerLast(i);
//这里判断，当窗口成型时，拿到队列的第一个索引值代表当前窗口最大值
if(i >= k - 1){
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}12.最小覆盖子串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。题解：
这题好懂，但难写
用两个哈希表（或数组）分别记录：
need：t 中每个字符需要的次数window：当前窗口中每个字符出现的次数
滑动窗口
[left, right)：不断移动
right扩大窗口，直到窗口包含 t 的所有字符（满足条件）一旦满足，尝试移动
left缩小窗口，同时更新最短子串的位置直到不满足条件，再次移动
right
用一个
valid变量记录当前窗口中有多少个字符的计数已经满足need的要求，可以避免每次比较整个哈希表。关键优化： 只对在
t中出现的字符做计数和检查。
public class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return "";
}
int[] need = new int[128];
for (char c : t.toCharArray()) {
need[c]++;
}
// 计算需要匹配的不同字符种类数
int required = 0;
for (int count : need) {
if (count > 0) required++;
}
int[] window = new int[128];
int left = 0, right = 0;
int valid = 0; // 已满足的字符种类数
int start = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need[c] > 0) {
window[c]++;
if (window[c] == need[c]) {
valid++;
}
}
// 窗口已经覆盖 t 的所有字符
while (valid == required) {
// 更新最小窗口
if (right - left < minLen) {
minLen = right - left;
start = left;
}
// 移动 left 缩小窗口
char d = s.charAt(left);
left++;
if (need[d] > 0) {
if (window[d] == need[d]) {
valid--;
}
window[d]--;
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}13.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1]
输出：1示例 3：
输入：nums = [5,4,-1,7,8]
输出：23题解：
易错点：currentSum和maxSum初始值应该为数组的第一个元素的值而不是0
currentSum要比较当前索引位置i的值与本身相加后的值的大小，数组元素可能为负
class Solution {
public int maxSubArray(int[] nums) {
//记录当前子串最大和
int currentSum = nums[0];
//记录结果最大
int maxSum = nums[0];
//注意这里i从1开始
for(int i = 1;i < nums.length;i++){
//每次累加，取最大值
currentSum = Math.max(nums[i],currentSum + nums[i]);
//判断更新最大值
maxSum = Math.max(currentSum,maxSum);
}
return maxSum;
}
}14.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。题解：
class Solution {
public int[][] merge(int[][] intervals) {
// 1. 空数组直接返回
if (intervals == null || intervals.length == 0) {
return new int[0][];
}
// 2. 按区间的 左端点 从小到大排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 3. 用 list 保存结果，方便添加
List<int[]> res = new ArrayList();
// 先把第一个区间放进去
res.add(intervals[0]);
// 4. 遍历剩下的所有区间
for(int i = 1;i < intervals.length;i++){
// 拿到结果里最后一个区间
int[] last = res.get(res.size() - 1);
int[] current = intervals[i];
// 当前区间的起点 <= 最后一个区间的终点 → 重叠，需要合并
if(current[0] <= last[1]){
// 合并：更新终点为两者最大值
last[1] = Math.max(current[1],last[1]);
}
else{
// 不重叠 → 直接加入
res.add(current);
}
}
// 5. 把 list 转成 int[][] 返回
return res.toArray(new int[res.size()][]);
}
}15.轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]题解：
三次反转数组即可，只需要确定反转数组的范围即可，数组反转的范围可以通过k取模数组长度得到
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums,0,nums.length - 1);
reverse(nums,0,k - 1);
reverse(nums,k,nums.length - 1);
}
public void reverse(int[] nums,int start,int end){
while(start < end){
int t = nums[start];
nums[start] = nums[end];
nums[end] = t;
start++;
end--;
}
}
}16.除了自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]题解：
🎯 核心思想
对于数组中的每个位置 i，结果 = 左边所有元素乘积 × 右边所有元素乘积
那么我们就可以分为两次循环来计算，第一次先算左边乘积再算右边乘积
nums = [1, 2, 3, 4]
Step 1: 计算左乘积
┌──────────────┐
index: 0 1 2 3 │ 左乘积
nums: [1, 2, 3, 4] │
↓ ↓ ↓ ↓ │
left: [1, 1, 2, 6] │
↑ ↑ ↑ │
│ │ └── 1×2×3=6
│ └───── 1×2=2
└─────────── 1=1
Step 2: 从右向左乘右乘积
┌──────────────┐
right: 1 4 12 24 │ 右乘积
↑ ↑ ↑ ↑ │
nums: [1, 2, 3, 4] │
│ │ │ │ │
answer: [24,12,8,6] │ 最终结果
↑ ↑ ↑ ↑ │
│ │ │ └── 6×1=6
│ │ └───── 2×4=8
│ └──────── 1×12=12
└─────────── 1×24=24class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
// 第一次遍历：计算左边所有元素的乘积
// answer[i] = nums[0] * nums[1] * ... * nums[i-1]
answer[0] = 1;
for (int i = 1; i < n; i++) {
answer[i] = answer[i - 1] * nums[i - 1];
}
// 第二次遍历：从右向左，乘上右边所有元素的乘积
// rightProduct 表示 nums[i+1] * nums[i+2] * ... * nums[n-1]
int rightProduct = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] = answer[i] * rightProduct;
rightProduct *= nums[i]; // 为下一次循环准备
}
return answer;
}
}17.缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。题解：
先找规律，对于这题我们正整数的范围在【1，数值长度 + 1】
将数组进行“排序”这里的排序规则是：将nums[i]放到i - 1的位置上，排序完成之后我们可以遍历数组进行判断，判断逻辑：查看索引 i上的值是否为 i + 1，如果不是我们就完美得出未出现的正数 i + 1，如果遍历中判断结果全为TRUE，则说明数组元素值一定是【1，数组长度 + 1】区间内元素依次出现，那么没有出现的值就一定是数组长度+1；
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 将每个正整数放到正确的位置
for (int i = 0; i < n; i++) {
// 只处理 [1, n] 范围内的数
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
//将数值交换到正确位置：将nums[i]放到i - 1的位置
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
// 找到第一个位置不对的数
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}阶段思想汇总
一、哈希表（空间换时间）
二、双指针（夹逼 / 快慢）
三、滑动窗口（最长 / 最短 / 固定窗口）
口诀：右指针猛冲，左指针慢收，一遍走完，快慢双滑。
四、动态规划与贪心
五、巧妙的数组操作（原地 / 反转 / 前缀）
18.相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。核心思想：
将两个链表相互遍历一遍，两个指针走过的步数应该是相同的，那么在步数相同的情况下while循环退出情况：
1：a和b都是null，即不相交
2：a == b 即相交的节点
题解：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a= headA;
ListNode b = headB;
while(a != b){
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}19.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]示例 3：
输入：head = []
输出：[]题解：
原链表: 1 → 2 → 3 → 4 → 5
虚拟头: dummy → null
遍历 1:
1.next = dummy.next (null) → 1 → null
dummy.next = 1 → dummy → 1 → null
遍历 2:
2.next = dummy.next (1) → 2 → 1 → null
dummy.next = 2 → dummy → 2 → 1 → null
... 依次类推，最后得到 dummy → 5 → 4 → 3 → 2 → 1 → nullclass Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode();
ListNode p = head;
while(p != null){
ListNode next = p.next;
p.next = dummy.next;
dummy.next = p;
p = next;
}
return dummy.next;
}
}20.回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true示例 2：
输入：head = [1,2]
输出：false核心思路：
将链表各个节点的值放到数组中，然后通过双指针，判断双指针值是否相等来判断是否为回文
题解：
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> value = new ArrayList();
ListNode curr = head;
while(curr != null){
value.add(curr.val);
curr = curr.next;
}
int l = 0, r = value.size() - 1;
while(l < r){
if(value.get(l) != value.get(r)){
return false;
}
l++;
r--;
}
return true;
}
}21.环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。核心思想：
快慢指针，如果链表存在环，那么快指针会先一步进入环并且一直在环中前进，慢指针会慢一步进入环，快指针一定会在某个时刻与慢指针相遇，即套了慢指针若干圈
题解：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode a = head , b = head.next;
while(a != b){
if(b == null || b.next == null){
return false;
}
a = a.next;
b = b.next.next;
}
return true;
}
}将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
22.合并两个有序链表
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = []
输出：[]示例 3：
输入：l1 = [], l2 = [0]
输出：[0]核心思想：
对于这题主要自行构建链表，在循环中遍历l1,l2比较值来决定，将哪个节点拼接进新链表。
题解：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prevHead = new ListNode(-1);
ListNode prev = prevHead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
prev.next = l1;
l1 = l1.next;
}
else{
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return prevHead.next;
}
}23.两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]核心思路：
同时遍历两个链表，将对应位置的数字与低位进位相加，结果的个位生成新节点，十位作为进位传递给下一位。
题解：
统一处理长度不一致
循环条件设为：
l1 != null || l2 != null || carry != 0如果某个链表先走完，该位按
0处理（无需补 0，代码更简洁）
维护进位变量
carry每次计算：
sum = 当前位值 + 当前位值 + carry新节点值：
sum % 10下一位进位：
sum / 10（只能是 0 或 1，因为9+9+1=19）
处理最后的进位
当两个链表都遍历完，但
carry还为1时，需要额外创建一个节点1例：
[9,9] + [1]→ 输出[0,0,1]（99+1=100）
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null , tail = null;
int carry = 0;
while(l1 != null || l2 != null){
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if(head == null){
head = tail = new ListNode(sum % 10);
}
else{
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
if(carry > 0){
tail.next = new ListNode(carry);
}
return head;
}
}24删除链表倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1
输出：[]示例 3：
输入：head = [1,2], n = 1
输出：[1]核心思路：
快慢指针，first节点比second节点多走N步，之后first和slow同步向前走，当first节点走完链表时second就走到了倒数第N个位置。first先走，然后second同步推进，两个节点距离差值一直时N,所以当first到末尾时，second就指向了倒数第N个节点。
题解：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0,head);
ListNode first = head;
ListNode second = dummy;
for(int i = 0;i < n;i++){
first =first.next;
}
while(first != null){
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
快慢指针流派
流派一：同时从 head 出发（slow = head; fast = head）
这是最通用的写法，用于检测环和找上中点（偏右）。
java
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 循环结束：slow 落在“上中点”落点规律（找中点）：
节点数奇数（如
[1,2,3,4,5]）→ slow 停在3（正中间）。节点数偶数（如
[1,2,3,4]）→ slow 停在3（上中点，即中间偏右）。
适用场景：环形链表检测（Floyd判圈算法），因为同时起步能保证在环内必相遇。
流派二：fast 先走一步（slow = head; fast = head.next）
这是找下中点（偏左）和分割链表的黄金写法，常用于归并排序链表。
java
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 循环结束：slow 落在“下中点”落点规律（找中点）：
节点数奇数（
[1,2,3,4,5]）→ slow 停在3（正中间，与流派一相同）。节点数偶数（
[1,2,3,4]）→ slow 停在2（下中点，即中间偏左）。
为什么需要这个？ 当你要把链表切成两半（
left = head; right = slow.next; slow.next = null）时，用流派二，left永远比right长度相等或多一个节点。如果使用流派一切偶数链表（[1,2,3,4]），slow停在3，切出来左边[1,2,3]，右边[4]，长度严重失衡，递归排序会出问题（甚至死循环）。
流派三：从虚拟头节点（哑节点）出发（slow = dummy; fast = dummy）
这是删除倒数第 N 个节点或需要前驱节点时的标准起手式。
java
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy, fast = dummy;
// 让 fast 先走 n+1 步（或者一起走，终止条件不同）
while (fast.next != null) {
fast = fast.next;
if (n-- <= 0) slow = slow.next;
}
// 循环结束：slow 指向待删除节点的前驱
slow.next = slow.next.next;核心差异：
slow不再是目标节点本身，而是目标节点的前一个节点。为什么这么起手：因为单链表删除节点必须知道前驱。如果
slow从head出发，走到最后slow正好指向要删除的节点，你无法删除它（拿不到前驱）。从dummy出发，slow天然滞后一步，直接slow.next = slow.next.next就完成了。
流派四：数组中的快慢指针（slow = 0; fast = 0 或 fast = 1）
这对应 LeetCode 27（移除元素） 或 26（删除有序数组重复项）。
起手相同（
slow=0; fast=0）：slow指向已处理区域的末尾，fast作为探针。每次先处理nums[fast]，再赋值给nums[slow]，最后slow++。起手差一（
slow=0; fast=1）：用于比较相邻元素去重。因为fast从 1 开始，slow指向待填充位置，通常配合nums[fast] != nums[fast-1]使用，避免处理空数组时越界。
📊 终极对比表（链表场景）
💡 避坑指南
记住循环条件：
while(fast != null && fast.next != null)和while(fast.next != null && fast.next.next != null)截然不同，前者让 slow 停在中点，后者容易让 slow 偏移，需要配套起手方式使用。画图调试：拿
[1,2,3,4]手动画两步，就能立刻明白为什么流派一停在 3，流派二停在 2。面试回答话术：如果面试官问为什么这么写，回答 “为了让慢指针指向我期望的落点，方便后续断链或删除操作”，直接满分。