18. 4Sum
1. Description
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.
2. Example
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [], target = 0
Output: []
3. Constraints
- 0 <= nums.length <= 200
- $-10^9$ <= nums[i] <= $10^9$
- $-10^9$ <= target <= $10^9$
4. Solutions
My Accepted Solution
n = m_nums.size()
Time complexity: O($n^3$)
Space complexity: O(n)
class Solution {
public:
// vector<vector<int>> fourSum(vector<int>& nums, int target)
vector<vector<int>> fourSum(vector<int> &m_nums, int target)
{
vector<vector<int>> result;
if(m_nums.size() < 4) return result;
sort(m_nums.begin(), m_nums.end());
for(int i = 0; i < m_nums.size() - 3; i++)
{
if(i > 0 && m_nums[i] == m_nums[i-1]) continue;
if(m_nums[i] + m_nums[i+1] + m_nums[i+2] + m_nums[i+3] > target) break;
if(m_nums[i] + m_nums[m_nums.size()-3] + m_nums[m_nums.size()-2] + m_nums[m_nums.size()-1] < target) continue;
for(int j = i + 1; j < m_nums.size() - 2; j++)
{
if(j > i + 1 && m_nums[j] == m_nums[j-1]) continue;
if(m_nums[i] + m_nums[j] + m_nums[j+1] + m_nums[j+2] > target) break;
if(m_nums[i] + m_nums[j] + m_nums[m_nums.size()-2] + m_nums[m_nums.size()-1] < target) continue;
int left = j + 1, right = m_nums.size() - 1;
while(left < right)
{
int sum = m_nums[left] + m_nums[right] + m_nums[i] + m_nums[j];
if(sum < target) left++;
else if(sum > target) right--;
else
{
result.push_back(vector<int>{m_nums[i], m_nums[j], m_nums[left], m_nums[right]});
do{left++;} while(m_nums[left] == m_nums[left-1] && left < right);
do{right--;} while(m_nums[right] == m_nums[right+1] && left < right);
}
}
}
}
return result;
}
};