从最简单的两数求和开始

LeetCode1

题目： 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

思路：

两个数求和时，使用左右指针的方法，实现对容器进行排序，当arr[left] + arr[right] > target时，right–,当arr[left] + arr[right] < target 时，left++，这样就可以遍历容器来求两数和了，但是遍历的时候还有一个问题，我们不需要输出重复的元素，因此又多了一个条件，首先将当前的left和right的值保存在numleft和numright中，当arr[left] + arr[right] > target时，先判断刚arr[left]是不是等于arr[numleft]，如果等于那么就给left++，直到arr[left]!=arr[numleft]为止；right也是这样。

vector> getresult(vector& arr,int target) {sort(arr.begin(), arr.end());vector> res;int left = 0;int right = arr.size() - 1;while (left < right) {int sum = arr[left] + arr[right];int numleft = left;int numright = right;if (sum < target) {while (left < right&&arr[left]==arr[numleft]) {left++;}}else if (sum>target) {while (left < right && arr[right]==arr[numright]) {right--;}	}else {res.push_back({ arr[left],arr[right] });while (left < right && arr[left] == arr[numleft]) {left++;}while (left < right && arr[right] == arr[numright]) {right--;}}}return res;
}int main() {vector s = { 1,1,1,2,2,3,3 };int target = 4;vector> result = getresult(s,target);for (vector>::iterator it = result.begin(); it != result.end();it++) {for (vector::iterator vit = (*it).begin(); vit != (*it).end();vit++) {cout << *vit << " ";}cout << endl;}return 0;
}

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-arr[i]，这样将返回的两数的和再遍历，加上当前的arr[i]的值一起存进一个容器中，就满足了三个数的和，这里还需要注意跳过第一个数字重复的情况，否则可能会出现重复的结果。

vector> getresult(vector& arr,int start,int target) {vector> res;int left = start;int right = arr.size() - 1;while (left < right) {int sum = arr[left] + arr[right];int numleft = left;int numright = right;if (sum < target) {while (left < right&&arr[left]==arr[numleft]) {left++;}}else if (sum>target) {while (left < right && arr[right]==arr[numright]) {right--;}	}else {res.push_back({ arr[left],arr[right] });while (left < right && arr[left] == arr[numleft]) {left++;}while (left < right && arr[right] == arr[numright]) {right--;}}}return res;
}vector> getthreeresult(vector& arr,int target) {sort(arr.begin(),arr.end());vector> res;int sz = arr.size();for (int i = 0; i < sz;i++) {vector> tworesult = getresult(arr,i+1,target-arr[i]);for (vector ress:tworesult) {ress.push_back(arr[i]);res.push_back(ress);}//跳过第一个数字重复的情况，否则可能会出现重复结果while (i < sz - 1 && arr[i] == arr[i + 1]) i++;}return res;
}int main() {vector s = { -1,0,1,2,-1,4 };int target = 0;vector> result = getthreeresult(s,target);for (vector>::iterator it = result.begin(); it != result.end();it++) {for (vector::iterator vit = (*it).begin(); vit != (*it).end();vit++) {cout << *vit << " ";}cout << endl;}return 0;
}

LeetCode18

题目： 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

思路：

四数之和与三数之和类似，循环遍历第一个元素，剩下的三个之和就是target-arr[i]，并且要注意跳过第一个数字重复的情况。

vector> getresult(vector& arr,int start,int target) {vector> res;int left = start;int right = arr.size() - 1;while (left < right) {int sum = arr[left] + arr[right];int numleft = left;int numright = right;if (sum < target) {while (left < right&&arr[left]==arr[numleft]) {left++;}}else if (sum>target) {while (left < right && arr[right]==arr[numright]) {right--;}	}else {res.push_back({ arr[left],arr[right] });while (left < right && arr[left] == arr[numleft]) {left++;}while (left < right && arr[right] == arr[numright]) {right--;}}}return res;
}vector> getthreeresult(vector& arr,int start,int target) {vector> res;int sz = arr.size();for (int i = start; i < sz;i++) {vector> tworesult = getresult(arr,i+1,target-arr[i]);for (vector ress:tworesult) {ress.push_back(arr[i]);res.push_back(ress);}//跳过第一个数字重复的情况，否则可能会出现重复结果while (i < sz - 1 && arr[i] == arr[i + 1]) i++;}return res;
}
vector> getfour(vector& arr, int target) {sort(arr.begin(),arr.end());int sz = arr.size();vector> resss;for (int i = 0; i < sz; i++) {vector> threeresult = getthreeresult(arr,i+1,target-arr[i]);for (vector re : threeresult) {re.push_back(arr[i]);resss.push_back(re);}//跳过第一个数字重复的情况，否则可能会出现重复结果while (i < sz - 1 && arr[i] == arr[i + 1]) i++;}return resss;
}
int main() {vector arr = { -1,0,1,2,-1,4 };int target = 0;vector> result = getfour(arr,target);for (vector>::iterator it = result.begin(); it != result.end();it++) {for (vector::iterator vit = (*it).begin(); vit != (*it).end();vit++) {cout << *vit << " ";}cout << endl;}return 0;
}