class Solution {
public:
std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
// 创建vector<vector<int>> 类型的变量不赋值时，不会自动包含任何随机值，而是保持为空的状态
// 等价于 std::vector<std::vector<int>> res = {};
std::vector<std::vector<int>> res;
// 本题只要求返回vector元素，可排列vector。若要求返回下标，以下方法不可行
sort(nums.begin(), nums.end());
for (int k=0; k<nums.size();k++){
if (nums[k]>target && target>=0) return res; // 剪枝一，避免[-4,-1,0,0] -5
if (k>0 && nums[k]==nums[k-1]) continue; // 对nums[k]去重
for (int i=k+1; i<nums.size(); i++){
if (nums[k]+nums[i]>target && target>=0) break; // 剪枝二
if (i>k+1 && nums[i]==nums[i-1]) continue; // i=k+2,k+3,... 对nums[i]去重
int left = i+1, right = nums.size()-1; // 双指针
while(left<right){
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if ((long)nums[k]+nums[i]+nums[left]+nums[right] > target) right--;
else if ((long)nums[k]+nums[i]+nums[left]+nums[right] < target) left++;
else {
//res.push_back(vector<int>{nums[i], nums[left], nums[right]});编译器会推断容器类型
res.push_back({nums[k], nums[i], nums[left], nums[right]});
while (left<right && nums[left]==nums[left+1]) left++; // 对nums[left]去重
while (left<right && nums[right]==nums[right-1]) right--; // 对nums[right]去重
left++, right--;
}
}
}
}
return res;
}
};