刷Leetcode的第一题的时候，就是4-sum问题，然后脑子里开始回想算法课中接触过的2-sum和3-sum问题，发现只有零星的片段，没有系统的优化设计过程，所以在这里进行整理。 有任何问题欢迎评论区或私信交流~
对于给定的一个整型数组，求解其中两个元素和为零的整数对以及整数对的数目。（不允许包含重复的整数对，整数对是无序的）
问题解决（1）暴力算法O(n2)
用两层循环来维持两个元素的指针，依次判断元素的和是否为0。 注意：为了维持数对的不重复性，维护的两个指针也应该有顺序区分。
void TwoSum(vector<int> arr){ int res = 0; vector<pair<int,int> > ans; memset(ans,0,sizeof(ans)); for(int i = 0;i<arr.size();i++){ for(int j = i+1;j<arr.size();j++){ if(arr[i]+arr[j] == 0){ res++; ans.push_back(make_pair(arr[i],arr[j]); } //ans中存放的就是结果数对，res中存放的就是符号要求的数对数量 }（2）归并排序+二分查找
【核心思路】 先将元素进行排序，对于每一个元素a[i]，当且仅当-a[i]也存在于数组中且a[i]≠0时，a[i]存在于满足要求的数对中。 【复杂度分析】 对于每一个-a[i]进行查询的时候，使用二分查找，这要求数组是有序的，故先要用归并排序对数组进行排序。 整个算法的复杂度为O(NlogN)
①折半查找的实现
【递归实现】
//二分查找返回符合要求的数组下标，若查询不到符合要求的下标，则返回-1 int binary_search(int a[],int low,int high,int key){ if(low >high} return -1; int mid = (low + high) / 2; if(a[mid] == key) return mid; if(a[mid] > key) return binary_search(a,low,mid-1,key); else return binary_search(a,mid+1,high,key); }【非递归实现】
//二分查找返回符合要求的数组下标，若查询不到符合要求的下标，则返回-1 int binary_search(int a[],int low,int high,int key){ while(low<=high){ int mid = (low + high) / 2; if(a[mid] == key) return mid; if(a[mid] > key) high = mid - 1; else low = mid + 1; } return -1; }②归并排序的实现
归并排序是分治算法常见的应用之一，关于其实现、优化以及自顶向下和自底向上的两种不同思想，可以参考这篇博文《归并排序算法的分析和实现》
③线性对数级别的TwoSum问题的算法伪码
void TwoSumFast(vector<int> arr){ int res = 0; for(int i = 0;i<arr.size();i++){ if(binary_search(arr,0,arr.size()-1,-arr[i])>i res++; } //res中存放的就是符号要求的数对数量 }算法使用二分查找，对于数组中的每一个元素a[i]，针对键值-a[i]进行查找。如果结果为j且j>i（维持这个条件主要是为了防止重复），我们就将计数器加1. 这个简单的条件猜测是覆盖了三种情况：
如果二分查找不成功则会返回01，那么我们不会增加计数器的值如果二分查找返回的j>i，我们就有a[i]+a[j] = 0，增加计数器的值。如果二分查找返回的j在0和i之间，我们也有a[i] + a[j] = 0，但不能增加计数器的值，以避免重复计数。对于给定的一个整型数组，求解其中三个元素和为零的整数对以及整数对的数目。（不允许包含重复的整数对，整数对是无序的）
问题解决（1）暴力算法O(n2)
用三层循环来维持三个元素的指针，依次判断元素的和是否为0。 注意：为了维持数对的不重复性，维护的三个指针也应该有顺序区分。 代码和Two-sum问题的暴力解法很相似，这里略过。
（2）归并排序+二分查找
【核心思路】 先将元素进行排序（不论是两数和还是三数和问题，均假设所有整数各不相同），对于元素a[i]和a[j]，当且仅当-(a[i]+a[j])也存在于数组中时，整数对（a[i],a[j]）为某个和为0的三元组的一部分。 【复杂度分析】 对于每一个整数对的和的相反数-(a[i]+a[j])进行查询的时候，使用二分查找，这要求数组是有序的，故先要用归并排序对数组进行排序。 整个算法的复杂度为O(N2logN)
在这种情况下，排序的成本反而是次要因素。
void TwoSumFast(vector<int> arr){ int res = 0; for(int i = 0;i<arr.size();i++){ for(int j = =i+1;j<arr.size();j++){ if(binary_search(arr,0,arr.size()-1,-(arr[i]+arr[j]))>j) res++; } //res中存放的就是符号要求的数对数量 }对于给定的一个整型数组，求解其中四个元素和为给定目标值target的整数对以及整数对的数目。（不允许包含重复的整数对，整数对是无序的）
问题求解①当然也可以考虑之前都用过的暴力求解方法，四层循环，依次验证。但是时间开销会很大，对于数据量过大的用例是无法通过的。
②双指针思想
题解来源于《双指针解法-参照三数之和》
【核心思路】 维护了四个指针a,b,c,d（a<b<c<d），起初的时候固定最小的a和b在数组的最左侧，c = b+1,d = size-1，c和两个指针实行包夹求解。保存使得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; } };如果把四数求和的问题中的双指针思想弄明白了，那么对于二数和、三数和问题同样可以借鉴这个思想。 比如二数和的时候，只需要两个指针，分别从左和右进行包夹即可。 三数和的时候，需要维持一层的循环，循环内就是两个指针的包夹。
在双指针思想中，循环控制的是基准，相当于为包夹定下范围和边界；包夹是进行数值选择，确定最终的解。
