Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c= 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]题目:求满足和为0的所有三元组。
思路:先对nums进行排序,那么要找到满足a+b+c=0的三元组,等价于找b+c=-a。那么我们可以把nums[i]当成a,在nums[i+1...]中进行查找,设置两个位置指针,分别指向最前和最后,判断两者的和的大小来不断调整位置指针的位置,使得nums[left]+nums[right]=-nums[i]即可。注意跳过相同的元素。
工程代码下载
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(); vector<vector<int>> res; for(int i = 0; i < n; ++i){ if(nums[i] > 0) break; int target = - nums[i]; int left = i + 1, right = n - 1; while(left < right){ int sum = nums[left] + nums[right]; if(sum < target) ++left; else if(sum > target) --right; else{ vector<int> triplet{nums[i], nums[left], nums[right]}; res.push_back(triplet); //处理重复的triplet[1] while(left < right && nums[left] == triplet[1]) ++left; //处理重复的triplet[2] while(left < right && nums[right] == triplet[2]) --right; } } //处理重复的triplet[0] while(i+1 < n && nums[i] == nums[i+1]) ++i; } return res; } };Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).题目:在nums中找出三元组使其和最接近target,返回该三元组的和。
思路:同15. 3Sum。用closest表示与target之间的最小差别,可正可负。
工程代码下载
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int closest = INT_MAX; int n = nums.size(); for(int i = 0; i < n; ++i){ int left = i+1, right = n-1; while(left < right){ int tmp = nums[i] + nums[left] + nums[right] - target; if(abs(tmp) < abs(closest)) closest = tmp; if(tmp < 0) ++left; else if(tmp > 0) --right; else return target + closest; } } return target + closest; } };