电子商务网站建设资料,百度域名排行,为什么wordpress的子主题样式无效,建筑工人信息平台三数之和
三数之和
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重…三数之和
三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。 思路先排序保证数组不降序排列为了后续去重操作。从左往右一次固定一个数 tmp 在右边使用双指针算法找到两个数的和等于 - tmp 的情况等价于三个数的和等于0找到之后不停止继续遍历直至找到固定数为 tmp 的情况下的所有情况右移 tmp 位置直至 tmp 到达区间的最倒数第三个位置。
‘不同的三元组’去重操作在找到一组目标值后因为已经排好序了所以只需要让双指针向中间移动如果移动后值等于之前值的话就再次移动直到找到一个不重复的位置
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint vv;int tmp 0;int tmpi nums.size()-3;while(tmp tmpi){if(nums[tmp]0) break;int left tmp 1;int right nums.size() - 1;while(left right){if(nums[left] nums[right] -nums[tmp]) right --;else if(nums[left] nums[right] -nums[tmp]) left ;else{vv.push_back({nums[left],nums[right],nums[tmp]});right--;left;while(nums[right1] nums[right] right left) right--;while(nums[left-1] nums[left] left right) left;}}tmp;while(nums[tmp-1]nums[tmp] tmp tmpi) tmp;}return vv;}
};
四数之和
四数之和
给你一个由 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
你可以按 任意顺序 返回答案 。 思路四数之和可以看做是先固定一个数区间右边就当做三数之和来处理。先固定一个数 a右边当做三数之和再在三数之和中固定一个数 b在区间右边利用双指针来处理即可。
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint vv;if(nums.size()4) return vv;sort(nums.begin(),nums.end());size_t n nums.size();for(size_t i 0;i n - 4;){// 固定最左边的数 nums[i]三数之和的目标变为 target - nums[i]long long target1 target - nums[i];for(int j i 1;j n-3;){//固定num[i]右边的数 nums[j]双指针的目标变为 target - nums[i] - nums[j]long long target2 target1 - nums[j];size_t left j1, right n -1;while(left right){if(nums[left] nums[right] target2) right--;else if(nums[left] nums[right] target2) left;else{vv.push_back({nums[i],nums[j],nums[left],nums[right]});left;right--;while(nums[left] nums[left-1] leftright) left;while(nums[right] nums[right1] leftright) right--;}}j;while(nums[j] nums[j-1] j n-3) j;}i;while(nums[i] nums[i-1] i n-4) i;}return vv;}
};
