今天和大家聊的问题叫做四数之和 ，我们先来看题面：
https://leetcode-cn.com/problems/4sum/
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
题意
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。
样例
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
题解
四数之和与前面三数之和的思路几乎是一样的 。在前面的基础上多添加一个遍历的指针 。
使用四个指针(a<b<c<d)。固定最小的a和b在左边，c=b+1,d=_size-1 移动两个指针包夹求解。保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移，偏小时c右移。c和d相遇时，表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环，当b循环结束后。a++，进入下一轮a循环。即(a在最外层循环，里面嵌套b循环，再嵌套双指针c,d包夹求解)。
class Solution{ public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); vector<vector<int> > res; if(nums.size()<4) return res; int a,b,c,d,_size=nums.size(); for(a=0;a<=_size-4;a++){ if(a>0&&nums[a]==nums[a-1]) continue; //确保nums[a] 改变了 for(b=a+1;b<=_size-3;b++){ if(b>a+1&&nums[b]==nums[b-1])continue; //确保nums[b] 改变了 c=b+1,d=_size-1; while(c<d){ if(nums[a]+nums[b]+nums[c]+nums[d]<target) c++; else if(nums[a]+nums[b]+nums[c]+nums[d]>target) d--; else{ res.push_back({nums[a],nums[b],nums[c],nums[d]}); while(c<d&&nums[c+1]==nums[c]) //确保nums[c] 改变了 c++; while(c<d&&nums[d-1]==nums[d]) //确保nums[d] 改变了 d--; c++; d--; } } } } return res; } }; 作者：misakasagiri-2 链接：https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-jie-fa-can-zhao-san-shu-zhi-he-ge-/
今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
