天门市住房和城乡建设网站,物业宣传软文,wordpress如何压缩图片,市场调研的重要性四数之和 1. 题目解析2. 讲解算法原理3. 编写代码 1. 题目解析 题目地址#xff1a;四数之和 2. 讲解算法原理 首先对输入的数组进行排序#xff0c;以便后续使用双指针法。初始化一个空的二维向量 ret#xff0c;用于存储结果。对数组中的每个元素 nums[i] 进行遍历#… 四数之和 1. 题目解析2. 讲解算法原理3. 编写代码 1. 题目解析 题目地址四数之和 2. 讲解算法原理 首先对输入的数组进行排序以便后续使用双指针法。初始化一个空的二维向量 ret用于存储结果。对数组中的每个元素 nums[i] 进行遍历
使用长整型变量 a 存储 target - nums[i]将四数之和问题转化为三数之和问题。对于每个元素 nums[j]其中 j 从 i1 开始遍历 初始化两个指针 left 和 right分别指向 j1 和数组末尾。使用长整型变量 b 存储 a - nums[j]。在 left right 的条件下进行循环 计算当前指针所指元素的和 sum nums[left] nums[right]。如果 sum b则将 left 右移一位。如果 sum b则将 right 左移一位。如果 sum b说明找到了一组解将 {nums[left], nums[right], nums[j], nums[i]} 加入到 ret 中。 然后将 left 右移一位right 左移一位继续寻找下一组解。同时需要进行去重处理即跳过所有与当前值相同的元素以防止重复的解。 在每次循环结束后将指针 j 右移一位继续寻找下一个元素的解。 同样需要进行去重处理跳过所有与当前值相同的元素。 在外层循环结束后将指针 i 右移一位继续寻找下一个元素的解。 同样需要进行去重处理跳过所有与当前值相同的元素。 最后返回结果 ret。 3. 编写代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorint ret;int left,right,sum;int nnums.size();for(int i0;in;){long long atarget-nums[i];for(int ji1;jn;){leftj1,rightn-1;long long ba-nums[j];while(leftright){sumnums[left]nums[right];if(sumb) left;else if(sumb) right--;else if(sumb){ret.push_back({nums[left],nums[right],nums[j],nums[i]});left;right--;while(leftright nums[left]nums[left-1])left;while(leftright nums[right]nums[right1])right--; } }j;while(jn nums[j]nums[j-1])j;}i;while(in nums[i]nums[i-1])i;}return ret;}
};
