双指针-18.四数之和-力扣(LeetCode)
一、题目解析
1.不重复
1.a，b，c，d互不相同
2.若两个四元组元素不一一对应，则认为两个四元组不重复
2.任意顺序
1.四元组内元素顺序任意
2.答案中四元组排列顺序任意
二、算法原理
解法1：排序+暴力枚举+利用set去重 时间复杂度为O(N^4)
用4个for循环枚举，时间复杂度为0(N^4)
解法2：排序+双指针+利用set去重 时间复杂度为O(N^2)
1. 固定i，j得到nums[i]、nums[j]
2.在j后的区间内，利用两数之和找到两个数，使这两个数的和等于target-nums[i]-nums[j]
这里有个小地方需要注意，在测试样例中会出现一组数据，使target-nums[i]-nums[j]的结果超出int的存储大小，可以使用强制类型转换解决
3.对于满足条件的四元组直接insert到set容器中，完成去重操作
解法3：排序+双指针+不用set去重 时间复杂度为0(N^2)
1. 固定i，j得到nums[i]、nums[j]
2.在j后的区间内，利用两数之和找到两个数，使这两个数的和等于target-nums[i]-nums[j]
这里有个小地方需要注意，在测试样例中会出现一组数据，使target-nums[i]-nums[j]的结果超出int的存储大小，可以使用强制类型转换解决
3.通过控制left和right，使其跳过重复元素；控制i和j，使其跳过重复元素
细节问题
1.不漏
在找到一个结果后，不要停，缩小区间继续寻找
2.越界问题
在控制left、right、i和j的时候，需要注意越界问题，避免越界访问导致程序崩溃
依旧先去尝试解法2，然后再去挑战解法3，来提升自己的代码能力
三、代码示例
解法2：
vector<vector<int>> fourSum(vector<int>& nums, int target){sort(nums.begin(),nums.end());//排序set<vector<int>> s;vector<vector<int>> vv;int a = 0,b = 0,n = nums.size();int left = 0,right = 0;for(int i = 0;i<n;i++)//控制i{for(int j = i+1;j<n;j++)//控制j{a = nums[i],b = nums[j];left = j+1,right = n-1;long long aim = (long long)target - (long long)a - (long long)b;//处理超出int的情况while(left<right){int sum = nums[left]+nums[right];if(sum>aim) right--;else if(sum<aim) left++;else{s.insert({a,b,nums[left],nums[right]});//这里插入大括号会自动转化为vector<int>left++;right--;}}}}for(auto e : s)//范围for，从s中依次取元素{vv.push_back(e);//尾差到vv中}return vv;}
解法3：
vector<vector<int>> fourSum(vector<int>& nums, int target){sort(nums.begin(),nums.end());//排序vector<vector<int>> vv;int left = 0,right = 0,n = nums.size();//size是指nums数组元素的多少for(int i = 0;i<n;){for(int j = i+1;j<n;){left = j+1,right = n-1;long long aim = (long long)target - (long long)nums[i] - (long long)nums[j];//处理超过int的情况while(left<right){int sum = nums[left]+nums[right];if(sum>aim) right--;else if(sum<aim) left++;else{vv.push_back({nums[i],nums[j],nums[left],nums[right]});//转化为vector<int>left++;right--;while(left<right && nums[left] == nums[left-1]) left++;//限制范围，控制left跳过重复元素while(left<right && nums[right] == nums[right+1]) right--;//同理}}++j;//这里代替for循环++功能，所以for处为空while(j<n && nums[j] == nums[j-1]) ++j;//限制范围，跳过重复元素}++i;//同理while(i<n && nums[i] == nums[i-1]) ++i;}return vv;}
};