河北云网站建设,网站设计苏州,wordpress 支持mkv播放器,贵德县建设局网站一、题目描述
18. 四数之和
给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] #xff08;若两个四元组元素一一对应#xff0c;则认为两个四元组重复#x… 一、题目描述
18. 四数之和
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。 二、题目解析
算法思想排序双指针
1、依次固定一个数a
2、在a后面的区间内用“三数之和”找到三个数使用这三个数的和等于target - a即可
同理对于三数之和的算法
1、依次固定一个数b
2、在b后面的区间内利用“双指针”找到两个数是这两个数的和等于target - a - b
处理细节问题
1、不重复
注意这里的去重和三数之和不同这里需要多一组去重在确定a时也是需要判断是否重复其余去重操作和判断三数之和是一样。
2、不漏
与三数之和一样在找到满足题目条件的一组元素之后需要继续寻找。 注意
这里的数据有溢出的风险不开long long见祖宗~ 三、原码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;//1、先排序sort(nums.begin(),nums.end());//2、利用双指针解决int n nums.size();for(int i 0;in;){//下面是三数之和for(int j i1;jn;){//防止数据溢出开long longlong long target2 (long long)target - nums[i] - nums[j];int left j1;int right n-1;while(left right){int sum nums[left] nums[right];if(sum target2) right--;else if(sum target2) left;else{ret.push_back({nums[i],nums[j],nums[right],nums[left]});left;right--;//去重left rightwhile(left right nums[left] nums[left-1]) left;while(left right nums[right] nums[right1]) right--;}}//去重jj;while(jn nums[j] nums[j-1]) j;}//去重ii;while(in nums[i] nums[i-1]) i;}return ret;}
};
