一:题目解析
题目链接:18. 四数之和 - 力扣(LeetCode)
注:本题是在上题的基础上讲解的:专题一_双指针_三数之和-CSDN博客
解析:和三数之区别在于找四元组和为targe的数字 而不是0
二:算法原理
①:暴力
根据上题可知,暴力的最快版本如下,会超时,时间复杂度高达O(N^4)
1:先对原数组排序
2:暴力枚举加判断
3:利用unordered_set去重
注:先排序的益处很大,但暴力仅仅用来规避了去重前的组内排序,所以对时间复杂度无提升
②:优秀
核心依旧是三数排序的思路,唯一改变的在于,我们在最左面固定一个值,此时在这个值的右区间进行三数之和的算法即可!
三:代码编写
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());//排序int n = nums.size();vector<vector<int>> v;//返回值for(int i = 0;i<n;)//最外层的值的固定 相较于三数之和的区别所在!!{for(int j=i+1;j<n;)//所有j也得从i+1开始! 而三数之和是从0开始!{long long target2 = (long long)target-nums[i]-nums[j];//一定要long long类型 否则会溢出产生截断int left = j+1,right = n-1;//左指针从j+1 开始 右指针从最后一个元素开始while(left<right){int sum = nums[left]+nums[right];if(sum<target2) left++;else if(sum>target2) right--;else{v.push_back({nums[i],nums[j],nums[left],nums[right]});left++,right--;//双指针去重while(left<right && nums[left-1] == nums[left]) left++;while(left<right && nums[right+1] == nums[right]) right--;}}//j下标固定的元素去重j++;while(j<n && nums[j-1]==nums[j]) j++;}//i下标固定的元素去重i++;while(i<n && nums[i-1]==nums[i]) i++;}return v;}
};
解释:
1:因为四元组的和要为target,所以当到双指针的时候,双指针的和sum应该为:target-nums[i]-nums[j]!
2:一定要用long long类型,因为在 四数之和 问题中,target
和 nums[i]
、nums[j]
可能是 大整数,如果直接计算 target - nums[i] - nums[j]
,可能会发生 整数溢出!尤其当 nums[i] 和 nums[j] 是很大的负数时!
3:v进行push_back的时候,一定按照大小顺序进行push_bcak,如:nums[i],nums[j],nums[left],nums[right]