高端企业网站建设核心,合肥专业手机网站制作价格,用什么做网站 优化,网易企业邮箱密码格式题目描述
给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] #xff08;若两个四元组元素一一对应#xff0c;则认为两个四元组重复#xff09;#xff1a; …题目描述
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d n
a、b、c 和 d 互不相同
nums[a] nums[b] nums[c] nums[d] target你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2
输入nums [2,2,2,2,2], target 8
输出[[2,2,2,2]]提示
1 nums.length 200
-109 nums[i] 109
-109 target 109分析思路
它的方法与三数之和思路一样因为多了一个数需要在三数之和的基础上在外层套了一层for循环。 这里面的重点是外层for循环去重和第二层的for循环去重与三数之和存在差异具体的情况需要仔细做讨论。这里我先给出代码后面再来看一下这道中等题。
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint result;sort(nums.begin(), nums.end());for (int k 0; k nums.size(); k) {// 剪枝处理if (nums[k] target nums[k] 0) {break; // 这里使用break统一通过最后的return返回}// 对nums[k]去重if (k 0 nums[k] nums[k - 1]) {continue;}for (int i k 1; i nums.size(); i) {// 2级剪枝处理if (nums[k] nums[i] target nums[k] nums[i] 0) {break;}// 对nums[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 ((long) nums[k] nums[i] nums[left] nums[right] target) {right--;// nums[k] nums[i] nums[left] nums[right] target 会溢出} else if ((long) nums[k] nums[i] nums[left] nums[right] target) {left;} else {result.push_back(vectorint{nums[k], nums[i], nums[left], nums[right]});// 对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;}
};
