【LeetCode 17】5.7四数之和

【LeetCode 17】5.7四数之和

【LeetCode 17】5.7四数之和

文章目录

​​【LeetCode 17】5.7四数之和​​​​一、题意​​​​二、解题过程​​

一、题意

二、解题过程

在三数之和的基础上在套一层for循环：

​​15.三数之和​​

class Solution {public: vector> fourSum(vector& nums, int target) { vector> result; sort(nums.begin(), nums.end()); for (int k = 0; k < nums.size(); k++) { // 这种剪枝是错误的，这道题目target 是任意值 // if (nums[k] > target) { // return result; // } // 去重 if (k > 0 && nums[k] == nums[k - 1]) { continue; } for (int i = k + 1; i < nums.size(); i++) { // 正确去重方法 if (i > k + 1 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.size() - 1; while (right > left) { // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出 if (nums[k] + nums[i] > target - (nums[left] + nums[right])) { right--; // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出 } else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) { left++; } else { result.push_back(vector{nums[k], nums[i], nums[left], nums[right]}); // 去重逻辑应该放在找到一个四元组之后 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } } return result; }};

} } return result;}

};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。