LeetCode15三数之和 容易理解版本

题目： 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路：

逐个遍历数组，确定第一个元素后，剩下的两个数字就是和为 target - nums[i] 的两个数字了，因此将确定元素的下一个索引和target-nums[i]传给两个数相加和为某个数的函数，由该函数返回所有满足和为target-nums[i]的二维vector，将返回的结果遍历，如果结果不为空，每次循环将刚在确定的第一个数加进这个一维vector中组成一个和为0的三元组，再将这个三元组加入到vector中，在最后需要跳过第一个数组重复的情况，否则可能会出现重复的结果。

vector<vector<int>> twoSumtarget(vector<int>& nums,int start,int target) {int left = start;int right = nums.size() - 1;vector<vector<int>> res;while (left<right) {int leftnum = nums[left];int rightnum = nums[right];int sum = nums[left] + nums[right];if (sum <target) {while (left < right&&nums[left] == leftnum) {left++;}}else if (sum > target) {while (left < right && nums[right] == rightnum) {right--;}}else if(sum == target){res.push_back({ nums[left],nums[right] });while (left < right && nums[left] == leftnum) {left++;}while (left < right && nums[right] == rightnum) {right--;}}}return res;
}vector<vector<int>> threeSumtarget(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int numsize = nums.size();vector<vector<int>> res;for (int i = 0; i < numsize;i++) {vector<vector<int>> tuples = twoSumtarget(nums,i+1,target-nums[i]);//如果存在满足条件的二元组，再加上nums[i]结果就是三元组for (vector<int>& tuple:tuples) {tuple.push_back(nums[i]);res.push_back(tuple);}//跳过第一个数字重复的情况，否则可能会出现重复结果while (i < numsize - 1 && nums[i] == nums[i + 1]) i++;}return res;
}int main() {vector<int> c{ -1,0,1,2,-1,4 };int target = 0;vector<vector<int>> result= threeSumtarget(c,target);for (vector<vector<int>>::iterator it = result.begin(); it != result.end();it++) {for (vector<int>::iterator pit = (*it).begin(); pit != (*it).end();pit++) {cout<<*pit<<" ";}cout << endl;}return 0;
}