建大型门户网站,智能科技网站模板下载地址,提供企业网站建设价格,wordpress最近浏览15. 三数之和 题目 给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意#xff1a;答案中不可以包含重复的…
15. 三数之和 题目 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 题目链接 . - 力扣LeetCode 画图 和 文字 分析 这道题和 两数之和等于一个值 大体思路是一样的都是 排序 双指针思想 排完序后我们定义三个指针一个指向最后一个元素的位置一个指向首元素的位置另一个首元素的后一个位置 举例 输入 [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 先固定 k不动 如果三者指向的值相加为 0 ,则记录数据 再 j , k--如果三者指向的值 0 则 j如果三者指向的值 0 则 k-- 当 i j 结束里层循环 再 i , j i 1 , k n - 1 直到 i 1 k (外层循环) 做到以上只能说完成了完成了不漏掉每一种情况但现在还有去重的关键一步 去重需要我们在前面的基础上做更改 第一种情况 走完上面的步骤 : 判断现在 j 所指的内容 和 j - 1 所指内容是否相同直到不相同为止这里需要一个循环此时要么j 指向一个不和之前相重复的数要么越界 判断 k 同理 上面是里层循环的去重外层循环也可以去重 当结束里层循环完成后面的步骤 判断 i 所指向的内容 和 i - 1所指向的内容是否相同直到不相同为止 注意: 去重的时候因为循环的缘故一定要防止越界 代码 class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint t;sort(nums.begin(),nums.end());int i 0;while(i 2 nums.size() - 1){int j i 1;int k nums.size() - 1;;while(j k){if(nums[i] nums[j] nums[k] 0){k--;}else if(nums[i] nums[j] nums[k] 0){j;}else{vectorint x;x.push_back(nums[i]);x.push_back(nums[j]);x.push_back(nums[k]);t.push_back(x);int n nums[j];int m nums[k];k--;j;while(j k n nums[j]){j;}while(j k m nums[k]){k--;}}}int h nums[i];i;while(i 2 nums.size() - 1 h nums[i]){i;}}return t;}
}; 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 你可以按 任意顺序 返回答案 。 题目链接 . - 力扣LeetCode 画图 和 文字 分析 在 leetcode 15. 三数之和 基础之上做出的改变 思想排序 双指针思想 定义四个指针三个指针分别指向前三个元素的位置第四个指针指向最后一个元素的位置 举例 输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 后面的三个指针和之前的做法一模一样第一个指针在里层所有循环结束后 再判断现在 a 所指向的元素和 a - 1 所指向的元素是否相同 直到 a 2 d (外层循环结束) 注意 注意越界情况判断四数之和是否得到一个值这里容易由于数据过大发生整型溢出现象可以改成 longlong 类型 或者针对处理这一可能 代码 class Solution {
public:bool iscompare(int a,int b,int c,int d,int target){if(target 0 (a 0 b 0 c 0 d 0)){return false;}else if(target 0 (a 0 b 0 c 0 d 0)){return false;}else if(target 0 ((a 0 b 0 c 0 d 0) || (a 0 b 0 c 0 d 0))){return false;}else{return true;}}vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint s;int n nums.size() - 1;sort(nums.begin(),nums.end());int a 0;while(a 2 n){int b a 1;while(b 1 n){int c b 1;int d n;while(c d){if(!iscompare(nums[a],nums[b],nums[c],nums[d],target)){break;}if(nums[a] nums[b] target - nums[c] - nums[d] ){d--;}else if(nums[a] nums[b] target - nums[c] - nums[d] ){c;}else{vectorint t;t.push_back(nums[a]);t.push_back(nums[b]);t.push_back(nums[c]);t.push_back(nums[d]);s.push_back(t);int s1 nums[c];int s2 nums[d];d--;c;while(c d nums[c] s1){c;}while(c d nums[d] s1){d--;}}}int s3 nums[b];b;while(b 1 n nums[b] s3){b;}}int s4 nums[a];a;while(a 2 n nums[a] s4){a;}}return s;}
};
