leetcode18.四数之和(模仿三数之和)

    xiaoxiao2023-10-15  44

    这是根据上一篇的三数之和写出的四数之和。不同的是,此处固定的是i和j,移动的是k和e,具体原理同上一篇。

    class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; if(nums.size()<4) return res; sort(nums.begin(),nums.end()); for(int i=0;i<nums.size()-3;i++){ if(i>0&&nums[i]==nums[i-1]) continue; for(int j=i+1;j<nums.size()-2;j++){ if(j>i+1&&nums[j-1]==nums[j]) continue; for(int k=j+1,e=nums.size()-1;k<e;){ int sum=nums[i]+nums[j]+nums[k]+nums[e]; if(sum<target){ k++; }else if(sum>target){ e--; }else{ vector<int> a; a.push_back(nums[i]); a.push_back(nums[j]); a.push_back(nums[k++]); a.push_back(nums[e--]); res.push_back(a); while(k<e&&nums[k]==nums[k-1]) k++; while (k < e&&nums[e] == nums[e+1]) e--; } } } } return res; } };
    最新回复(0)