一、今日学习任务第14天 18. 四数之和建议 要比较一下本题和 454.四数相加II 的区别为什么 454.四数相加II 会简单很多这个想明白了对本题理解就深刻了。 本题 思路整体和 三数之和一样的都是双指针但写的时候 有很多小细节需要注意建议先看视频。题目链接https://leetcode.cn/problems/4sum/ 视频讲解https://www.bilibili.com/video/BV1DS4y147二、初次解题与思考在开始写代码之前我先对比了一下这两道题对比维度18. 四数之和454. 四数相加II数组个数1个数组4个独立数组数据来源同一个数组中取4个不同下标每个数组取1个元素重复处理需要手动去重因为同一数组有重复值不需要去重来自不同数组天然不重复常用解法排序双指针O(n³)分组哈希表O(n²)难度核心去重逻辑复杂容易漏/多思路直接实现简单为什么454会简单很多在454中四个数来自四个不同的数组即使数值相同也因为来源不同而被视为不同的组合。所以不需要考虑下标重复的问题不需要去重直接统计次数即可可以用哈希表做两两分组时间复杂度O(n²)而本题中四个数来自同一个数组必须保证四个下标互不相同且不能输出重复的四元组如[1,2,3,4]和[4,3,2,1]被视为相同。这就要在遍历时做去重剪枝复杂度大幅提升。2.2 解题思路推导做过“三数之和”就知道解决N数之和的通用思路是排序让数组有序方便双指针移动和去重固定前k-2个数用递归或循环固定前几个数双指针找最后两个数在剩余区间内用左右指针逼近对于四数之和外层循环固定第一个数i第二层循环固定第二个数j内层用双指针left和right找后两个数使nums[i]nums[j]nums[left]nums[right] target2.3 需要注意的细节根据题目评论区提示有几个坑要特别注意2. 与454.四数相加II的本质区别对比点18. 四数之和454. 四数相加II数组来源同一个数组取4个不同索引4个独立数组各取1个重复问题需要去重值相同算重复不需要去重来源不同解法思路排序双指针分组哈希表时间复杂度O(n³)O(n²)核心感悟454之所以简单是因为“去重”这个最麻烦的问题被天然规避了。这也提醒我分析题目时是否要去重会直接影响解法选择。3. 整数溢出问题的处理[-10⁹, 10⁹]范围内的四个数相加可能超出int范围约±2×10⁹必须用long。这是隐蔽又致命的坑通过这个题目我记住了多个大数求和优先考虑用long。4. 去重和剪枝的细节技巧整数溢出四个10⁹相加会超过int范围要用long类型去重时机每固定一个数后都要跳过重复值剪枝优化可以利用排序后的极值提前判断是否可能找到解三、写代码时遇到的问题问题1整数溢出导致的错误场景测试用例[1000000000,1000000000,1000000000,1000000000]target -294967296如果用int计算四个数的和会溢出变成负数导致判断错误。解决方案将和转换为long类型计算。问题2去重逻辑容易出错在固定第一个数时如果nums[i] nums[i-1]需要跳过。但如果写成if (nums[i] nums[i1]) continue就会漏掉[-2,-2,0,2]这种可能两个-2都要用到。正确做法在当前层循环中当i start且nums[i] nums[i-1]时跳过问题3left和right的去重时机找到一组解后移动指针时需要跳过重复值避免把相同的组合重复添加。四、代码五、今日收获1. 深刻理解了“N数之和”的通用解法从两数之和哈希表/双指针→ 三数之和固定一个双指针→ 四数之和固定两个双指针可以总结出通用模板排序预处理递归/循环固定前k-2个数最后两个数用双指针寻找每层都要去重和剪枝去重只在当前层去重i start nums[i] nums[i-1]不要写成nums[i] nums[i1]否则会漏解剪枝利用排序后的极值判断最小可能和、最大可能和提前退出或跳过