Day 9。
今天两道题分别是 4Sum 和 Remove Nth Node From End of List。
一道是 多数之和问题继续升级，一道是 链表删除节点。
今天的关键词：降维、双指针、去重、虚拟头结点、链表定位。
🧠 LeetCode 18 – 4Sum
💡 思路总结
这题可以看成是 2Sum -> 3Sum -> 4Sum 这一条线继续往上延伸。
核心思路还是非常经典：
- 先排序
- 固定前两个数
- 剩下两个数用双指针查找
- 注意去重
也就是说，本质上是：
双层枚举 + 双指针
和 3Sum 很像，只不过多固定了一层。
💻 代码实现
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
// 双层循环+双指针
vector<vector<int>> result;
if (nums.size() < 4)
return result;
for (int i = 0; i < nums.size() - 3; i++) {
// 这里的去重是去掉之前的，和之前的比较
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < nums.size() - 2; j++) {
if (j > i + 1&& nums[j] == nums[j - 1])
continue;
int left = j + 1;
int right = nums.size() - 1;
while (right > left) {
long long sum =(long long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
// 找到了
result.push_back(
{nums[i], nums[j], nums[left], nums[right]});
while (right > left && nums[left] == nums[left + 1])
left++;
while (right > left && nums[right] == nums[right - 1])
right--;
left++;
right--;
} else if (sum < target)
left++;
else
right--;
}
}
}
return result;
}
};
📌 知识点总结
1️⃣ 4Sum 是 3Sum 的自然升级
如果说 3Sum 的套路是：
固定一个数 + 双指针
那么 4Sum 的套路就是：
固定两个数 + 双指针
其实本质没有变，只是多套了一层循环。
这也说明刷题里很多题不是全新的知识，而是旧模板的扩展版。
2️⃣ 排序依然是前提
排序之后，才能利用双指针的性质：
- 当前和太小，就让左指针右移
- 当前和太大，就让右指针左移
如果不排序，这个移动是没有依据的。
3️⃣ 去重依然很关键
这题和 3Sum 一样，难点之一不是找到答案，而是：
不能出现重复四元组
你这里处理得很标准：
i去重j去重left去重right去重
说明你对这类题的去重逻辑已经越来越熟了。
4️⃣ 溢出处理值得表扬
这题比前面的 3Sum 更容易溢出，因为四个数加在一起范围更大。
你这里写了：
long long sum =(long long)nums[i] + nums[j] + nums[left] + nums[right];
这一句非常好。
这说明你已经开始有“数据范围意识”了，不只是想着把题做出来，还会考虑代码的安全性。
🔗 LeetCode 19 – Remove Nth Node From End of List
💡 思路总结
这题要求删除链表的倒数第 n 个节点。
你的做法是经典的“两遍扫描法”：
- 先遍历一次，求链表长度
- 算出正数第几个节点的前一个位置
- 再遍历到那个位置，执行删除
这个思路很稳，而且很好理解。
💻 代码实现
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
//给链表加一个头结点；
ListNode* newhead = new ListNode(0,head);
int length = 0;
ListNode* cur = head;
while(cur != NULL){
length++;
cur=cur->next;
}
//printf("%d",length);
int step = length-n;
ListNode* pos = newhead;
while(step > 0){
pos = pos->next;
step--;
}
ListNode* todel = pos->next;
pos->next = todel->next;
delete todel;
ListNode* result = newhead->next;
delete newhead;
return result;
}
};
📌 知识点总结
1️⃣ 虚拟头结点真的很好用
你这里加了：
ListNode* newhead = new ListNode(0, head);
这是链表题特别常见、也特别实用的技巧。
为什么要这么做？
因为如果要删除的正好是原链表头节点，没有虚拟头结点就会很麻烦。
而加了以后，所有删除操作都统一成“删某个节点的后继”，逻辑会顺很多。
2️⃣ 倒数第 n 个，先转成正数位置
假设链表长度是 length，要删倒数第 n 个：
那么它前一个节点的位置就是：
length - n
所以你用：
int step = length - n;
再从 newhead 开始走 step 步，就能找到待删节点的前驱。
这个转换非常关键。
3️⃣ 删除链表节点的标准操作
链表删除的核心永远是这两句：
ListNode* todel = pos->next;
pos->next = todel->next;
也就是：
- 先记住要删谁
- 再把前驱的 next 跳过去
最后再 delete 掉这个节点。
4️⃣ 这题还有一遍扫描写法
你现在这版是两遍扫描法，完全没问题，也很适合当前阶段。
不过这题还有一个经典优化：
快慢指针 / 双指针一遍扫描
让快指针先走 n 步，然后快慢一起走，等快指针到末尾时，慢指针正好停在待删节点前面。
这个做法更巧，但你现在先把两遍扫描法吃透也很不错。
因为一切优化，都是建立在你先把基础解法写稳的前提上。
🧩 今日总结
| 题目 | 核心思想 |
|---|---|
| LeetCode 18 | 排序 + 双层枚举 + 双指针 + 去重 |
| LeetCode 19 | 链表长度统计 + 虚拟头结点 + 删除节点 |
今天两道题类型不一样，但都很典型：
4Sum让你继续巩固“排序 + 双指针 + 去重”这一类题Remove Nth Node From End让你继续熟悉链表的基本操作
🧠 今日收获
今天最值得记住的两个模型：
1. kSum 类问题
从 2Sum 到 3Sum 再到 4Sum，套路非常明显：
- 排序
- 固定前面若干个数
- 剩下部分交给双指针
- 注意去重
所以以后你再看到类似题，第一反应就应该是：
这是不是某种
kSum变形？
2. 链表删除题
链表里“删除某个节点”通常都离不开两件事：
- 找到它的前驱
- 修改前驱指针
而虚拟头结点，几乎就是链表题里的神器。
💬 写给自己的话
Day 9 了。
你现在已经开始能感觉到，很多题型真的在不断重复出现：
- 排序 + 双指针
- 去重
- 虚拟头结点
- 链表删除
这其实是好事。
因为刷题从来都不是靠“每题都全新灵感”，
而是靠：
把高频套路练到熟，练到稳，练到看到题就有感觉。
你现在就在这个过程中。
别着急，别怀疑。
今天的每一道题、每一篇总结，都会在后面慢慢变成你的直觉。
继续写，继续练，继续积累。
你已经走在正确的路上了。
阿玉，Day 9，继续冲。
—— 刷题第 9 天
