leetcode_3.29
1.四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a b c d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
https://leetcode-cn.com/problems/4sum/
思路：类似三数求和,但是三数求和是和为0，因此不必排除重复，此处需要，故要求：每一种循环枚举到的下标必须大于上一重循环枚举到的下标
特别的本题还有一些剪枝操作：
在确定第一个数之后，如果 \textit{nums}[i] \textit{nums}[i 1] \textit{nums}[i 2] \textit{nums}[i 3]>\textit{target}nums[i] nums[i 1] nums[i 2] nums[i 3]>target，说明此时剩下的三个数无论取什么值，四数之和一定大于 \textit{target}target，因此退出第一重循环；
在确定第一个数之后，如果 \textit{nums}[i] \textit{nums}[n-3] \textit{nums}[n-2] \textit{nums}[n-1]<\textit{target}nums[i] nums[n−3] nums[n−2] nums[n−1]<target，说明此时剩下的三个数无论取什么值，四数之和一定小于 \textit{target}target，因此第一重循环直接进入下一轮，枚举 \textit{nums}[i 1]nums[i 1]；
在确定前两个数之后，如果 \textit{nums}[i] \textit{nums}[j] \textit{nums}[j 1] \textit{nums}[j 2]>\textit{target}nums[i] nums[j] nums[j 1] nums[j 2]>target，说明此时剩下的两个数无论取什么值，四数之和一定大于 \textit{target}target，因此退出第二重循环；
在确定前两个数之后，如果 \textit{nums}[i] \textit{nums}[j] \textit{nums}[n-2] \textit{nums}[n-1]<\textit{target}nums[i] nums[j] nums[n−2] nums[n−1]<target，说明此时剩下的两个数无论取什么值，四数之和一定小于 \textit{target}target，因此第二重循环直接进入下一轮，枚举 \textit{nums}[j 1]nums[j 1]。
代码：
class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> quadruplets; if (nums.size() < 4) { return quadruplets; } sort(nums.begin(), nums.end()); int length = nums.size(); for (int i = 0; i < length - 3; i ) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } if (nums[i] nums[i 1] nums[i 2] nums[i 3] > target) { break; } if (nums[i] nums[length - 3] nums[length - 2] nums[length - 1] < target) { continue; } for (int j = i 1; j < length - 2; j ) { if (j > i 1 && nums[j] == nums[j - 1]) { continue; } if (nums[i] nums[j] nums[j 1] nums[j 2] > target) { break; } if (nums[i] nums[j] nums[length - 2] nums[length - 1] < target) { continue; } int left = j 1, right = length - 1; while (left < right) { int sum = nums[i] nums[j] nums[left] nums[right]; if (sum == target) { quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]}); while (left < right && nums[left] == nums[left 1]) {//区别于固定，应该往后看是否相同！！！！ left ; } left ; while (left < right && nums[right] == nums[right - 1]) { right--; } right--; } else if (sum < target) { left ; } else { right--; } } } } return quadruplets; }};