本文主要是介绍【C++】双指针算法：四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题目
2.算法思路
这道题目十分困难，在leetcode上的通过率只有36%，大家要做好心理准备。
在做个题目前强烈建议大家先看看我的上一篇博客：有效三角形个数，看完之后再去leetcode上写一写三数之和，搞懂那两个题目之后再来看这道题目就比较容易了。
四数之和实际上和三数之和的思路差不多，只不过比三数之和多了一个步骤。
首先我们需要把这个数组排一下序，然后固定一个数a，然后在剩下的区间利用三数之和的思路解决。
三数之和的思路：
固定一个数b，然后定义两个指针left和right，分别从两端遍历数组，如果这四个数大于目标值则right--。如果这四个数小于目标值则left++。如果等于目标值，则记录下来，更新right或left,继续遍历。在这个过程中要注意：1.不漏 2.去重 3.防止整型溢出。
3.代码和提交结果
3.1提交结果
3.2代码
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> num_s;sort(nums.begin(),nums.end());for(int i=nums.size()-1;i>=3;){//固定数along long nums1=nums[i];for(int j=i-1;j>=2;){//固定数blong long nums2=nums[j];//防止计算四数之和时整型溢出int right=j-1,left=0;while(right>left){//计算四数之和if(nums1+nums2+nums[left]+nums[right]<target) left++;else if(nums1+nums2+nums[left]+nums[right]>target) right--;else{num_s.push_back({nums[left],nums[right],(int)nums2,(int)nums1});do{right--;//去重}while(right>left&&nums[right]==nums[right+1]);}}do{j--;//去重}while(j>=2&&nums[j]==nums[j+1]);}do{i--;//去重}while(i>=3&&nums[i]==nums[i+1]);}return num_s;}
};时间复杂度分析：
三次遍历数组相互嵌套，所以时间复杂度：O(n^3)。
这篇关于【C++】双指针算法：四数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
