之和(medium)"/>
[双指针]leetcode18:四数之和(medium)
题目:
题解:
- 双指针
- 本题在15.三数之和的基础上加了一层循环罢了,时间复杂度变为O(n3)了。
代码如下:
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> result;int size=nums.size();for(int a=0;a<size-3;++a){if(a>0&&nums[a]==nums[a-1])continue;//去重for(int b=a+1;b<size-2;++b)//以下代码与三数之和没有区别{if(b>a+1&&nums[b]==nums[b-1])continue;//去重int i=b+1,j=size-1;while(i<j){int sum=nums[a]+nums[b]+nums[i]+nums[j];if(sum<target)while(i<j&&nums[i]==nums[++i]);else if(sum>target)while(i<j&&nums[j]==nums[--j]);else{result.push_back(vector<int>{nums[a],nums[b],nums[i],nums[j]});while(i<j&&nums[i]==nums[++i]);while(i<j&&nums[j]==nums[--j]);}}}}return result;}
};
更多推荐
[双指针]leetcode18:四数之和(medium)
发布评论