今日学习内容四数之和今日任务 把18解决比较一下本题和 454.四数相加II 的区别为什么 454.四数相加II 会简单很多本题 思路整体和 三数之和一样的都是双指针但写的时候 有很多小细节需要注意。题目链接力扣18视频链接https://www.bilibili.com/video/BV1DS4y147US文章目录解题思路一、看题首要反应二、代码实现1.排序双指针法2.18与454的对比今日心得解题思路排序是前提通过排序既能方便去重又能利用双指针缩小搜索范围。两层循环固定前两个数外层循环固定第一个数nums[k]内层循环固定第二个数nums[i]。双指针找后两个数在i1到数组末尾的区间内用左右指针left和right寻找满足条件的后两个数。剪枝优化第一层剪枝若当前nums[k]大于目标值且为非负数后续和必然更大直接跳出循环第二层剪枝若nums[k]nums[i]大于目标值且为非负数同样提前终止内层循环。去重处理第一层去重k0且nums[k]nums[k-1]时跳过第二层去重ik1且nums[i]nums[i-1]时跳过双指针去重找到目标后跳过左右指针的重复值。注意整数溢出四个数相加可能超过int范围需用long long存储和剪枝条件不能简单用nums[k]target判断需结合非负条件**nums[k]0**避免负数目标值时的错误剪枝去重逻辑去重必须在同一层循环内进行例如内层循环的去重条件是ik1而非i0确保不会跳过合法的第一个元素。一、看题首要反应在三数之和基础上升级为四数求和核心要求找出数组中四个互不重复下标元素相加等于目标值且最终结果不能包含重复四元组。排序 双指针是最优解法固定两层循环枚举前两个数后两个数用左右指针收缩同时需要大量去重逻辑避免重复答案还要注意大数相加溢出问题。二、代码实现1.排序双指针法代码如下classSolution{public:vectorvectorintfourSum(vectorintnums,inttarget){vectorvectorintresult;sort(nums.begin(),nums.end());for(intk0;knums.size();k){if(nums[k]targetnums[k]0){break;}if(k0nums[k]nums[k-1]){continue;}for(intik1;inums.size();i){if(nums[k]nums[i]targetnums[k]nums[i]0){break;}if(ik1nums[i]nums[i-1]){continue;}intlefti1;intrightnums.size()-1;while(leftright){longlongsum(longlong)nums[k]nums[i]nums[left]nums[right];if(sumtarget){right--;}elseif(sumtarget){left;}else{result.push_back({nums[k],nums[i],nums[left],nums[right]});while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;left;right--;}}}}returnresult;}};2.18与454的对比18.四数之和同一个数组中选 4 个不重复下标元素求和 target必须去重 排序 双指针思路数组排序方便去重 双指针两层循环固定前两个数双指针找后两个数每一步都要去重454.四数相加II四个独立数组各选一个元素求和 0不用去重 不用排序 哈希表1 个数组找多数和就排序 双指针多个独立数组求和就分组 哈希表降时间复杂度去重判断来自同一个数组必须去重来自不同数组不用去重思路分成两组AB 和 CD用哈希表存 AB 所有和的出现次数遍历 CD找 0 - (CD) 在哈希表中是否存在累加次数就是答案今日心得给定一个整数数组和一个目标值找出所有不重复的四元组使得四数之和等于目标值。关键数组元素可正可负目标值也可能为负结果不能有重复四元组时间复杂度需控制在合理范围暴力解法O(n⁴)不可行。反思在去重逻辑上曾出现错误将ik1误写为i0导致部分合法结果被跳过。这说明边界条件的验证比核心逻辑更重要。坚持每日一题稳步提升算法能力继续加油