创想网站,wordpress 豆瓣 主题,访问国外的网站服务器无法访问,网站建设营销策划书18.四数之和
给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] #xff08;若两个四元组元素一一对应#xff0c;则认为两个四元组重复#xff09;#xff1…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
你可以按 任意顺序 返回答案 。 思路 四数之和和三数之和是一个思路都是使用双指针法, 基本解法就是在三数之和的基础上再套一层for循环。 三数之和 (opens new window)的双指针解法是一层for循环num[i]为确定值然后循环内有left和right下标作为双指针找到nums[i] nums[left] nums[right] 0。 四数之和的双指针解法是两层for循环nums[k] nums[i]为确定值依然是循环内有left和right下标作为双指针找出nums[k] nums[i] nums[left] nums[right] target的情况三数之和的时间复杂度是O(n^2)四数之和的时间复杂度是O(n^3) 。 那么一样的道理五数之和、六数之和等等都采用这种解法。 思考判断nums[k] target 就返回了吗 三数之和 可以通过 nums[i] 0 就返回了因为 0 已经是确定的数了四数之和这道题目 target是任意值。比如数组是[-4, -3, -2, -1]target是-10不能因为-4 -10而跳过。但是我们依旧可以去做剪枝逻辑变成nums[i] target (nums[i] 0 || target 0)就可以了。 核心代码 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; 这一期专栏记录将我每天的刷题希望各位的监督也希望和各位共勉。 追光的人终会光芒万丈
