LeetCode-18. 4SumLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/4sum/
Given an array nums
of n integers and an integer target
, are there elements a, b, c, and din nums
such that a + b + c + d = target
? Find all unique quadruplets in the array which gives the sum of target
.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
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()); if(nums[0]+nums[1]+nums[2]+nums[3]>target || nums[nums.size()-4]+nums[nums.size()-3]+nums[nums.size()-2]+nums[nums.size()-1]<target) return res; for(int i=0;i<nums.size()-3;i++){ auto target3 = target-nums[i]; if(nums[i+1]+nums[i+2]+nums[i+3]>target3) break; if(nums[nums.size()-3]+nums[nums.size()-2]+nums[nums.size()-1] < target3) continue; for(int j = i+1; j<nums.size()-2;j++){ auto target2 = target3-nums[j]; if(nums[j+1]+nums[j+2]>target2) break; if(nums[nums.size()-2]+nums[nums.size()-1]<target2) continue; int front = j+1, back = nums.size()-1; while(front<back) { auto sum2 = nums[front]+nums[back]; if(sum2<target2) front++; else if(sum2>target2) back--; else { res.push_back({nums[i],nums[j],nums[front++],nums[back--]}); while(front<back && nums[front-1]==nums[front]) front++; while(front<back && nums[back+1]==nums[back]) back--; } } while(j<nums.size()-2 && nums[j]==nums[j+1]) j++; } while(i<nums.size()-3 && nums[i]==nums[i+1]) i++; } return res; } };