网站建设制作确认单,网站建设策划书格式及范文,装修网站排名,网亿(深圳)信息科技有限公司双指针问题的常见剪枝#xff1a; 一.leecode第15题#xff1a;
给定一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a #xff0c;b #xff0c;c #xff0c;使得 a b c 0 #xff1f;请找出所有和为 0 且 不重复 的三元组。
示例 1…双指针问题的常见剪枝 一.leecode第15题
给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 a b c 使得 a b c 0 请找出所有和为 0 且 不重复 的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]示例 2
输入nums []
输出[]示例 3
输入nums [0]
输出[]提示
0 nums.length 3000
-105 nums[i] 105解答
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(), nums.end());vectorvectorint ans;int len nums.size();if(len 3){return ans;}//在[i1, len - 1]区间找到符合题意的元素for(int i 0; ilen-3; i){//剪枝 1if(nums[i] 0){return ans;}int left i 1, right len - 1;//剪枝 2if(i0 nums[i] nums[i - 1])continue;while(leftright){if(nums[left] nums[right] -nums[i]){right--;}else if(nums[left] nums[right] -nums[i]){left;}else{ans.push_back({nums[i], nums[left], nums[right]});//剪枝 3while(leftright nums[left] nums[left 1]){left;}while(leftright nums[right] nums[right-1]){right--;}left;right--;}}}return ans;}
};二.leecode第16题最接近的三书之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1
输入nums [-1,2,1,-4], target 1
输出2
解释与 target 最接近的和是 2 (-1 2 1 2) 。
示例 2输入nums [0,0,0], target 1
输出0提示
3 nums.length 1000
-1000 nums[i] 1000
-104 target 104解答
3 nums.length 1000
-1000 nums[i] 1000
-104 target 104class Solution {
public:int threeSumClosest(vectorint nums, int target) {sort(nums.begin(), nums.end());int len nums.size();int sum1 0;for(int i 0; ilen; i){sum1 nums[i];}if(len 3){return sum1;}int res nums[0] nums[1] nums[2];for(int i 0; ilen-3; i){//剪枝if(i0 nums[i] nums[i - 1]){continue;}int left i 1, right len - 1;while(left right){int sum nums[i] nums[left] nums[right];res abs(sum - target) abs(res - target) ? res : sum;if(nums[i] nums[left] nums[right] target){right--;}else if(nums[i] nums[left] nums[right] target){left;}else{return target;}}}return res;}
};
