【2/3/4-sum问题】算法设计剖析
【2/3/4-sum问题】算法设计剖析
刷Leetcode的第一题的时候，就是4-sum问题，然后脑子里开始回想算法课中接触过的2-sum和3-sum问题，发现只有零星的片段，没有系统的优化设计过程，所以在这里进行整理。
有任何问题欢迎评论区或私信交流~
Two-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，但不能增加计数器的值，以避免重复计数。
Three-sum问题
- 问题描述
对于给定的一个整型数组，求解其中三个元素和为零的整数对以及整数对的数目。（不允许包含重复的整数对，整数对是无序的）
- 问题解决
（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中存放的就是符号要求的数对数量
}
Four-sum问题
- 问题描述
对于给定的一个整型数组，求解其中四个元素和为给定目标值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;
}
};
如果把四数求和的问题中的双指针思想弄明白了，那么对于二数和、三数和问题同样可以借鉴这个思想。
比如二数和的时候，只需要两个指针，分别从左和右进行包夹即可。
三数和的时候，需要维持一层的循环，循环内就是两个指针的包夹。
在双指针思想中，循环控制的是基准，相当于为包夹定下范围和边界；包夹是进行数值选择，确定最终的解。