Написано: 26.02.2023
18. 4Sum
Задание.
Получен массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
-
0 <= a, b, c, d < n
-
a, b, c, и d – уникальные.
-
nums[a] + nums[b] + nums[c] + nums[d] == target
Пример 1.
Входные данные: nums = [1,0,-1,0,-2,2], target = 0
Результат: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Пример 2.
Входные данные: nums = [2,2,2,2,2], target = 8
Результат: [[2,2,2,2]]
Решение.
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size(), low, high, i, j, temp;
long newTarget;
sort(nums.begin(), nums.end());
vector<vector<int>> output;
for(i = 0; i < n-3; i++){
for(j = i+1; j < n-2; j++){
newTarget = (long)target - (long)nums[i] - (long)nums[j];
low = j+1;
high = n-1;
while(low < high){
if(nums[low] + nums[high] < newTarget) {
low++;
} else if(nums[low] + nums[high] > newTarget){
high--;
} else {
output.push_back({nums[i], nums[j], nums[low], nums[high]});
temp = low;
while(low < high && nums[low] == nums[temp]) low++;
temp = high;
while(low < high && nums[high] == nums[temp]) high--;
}
}
while(j+1 < n && nums[j] == nums[j+1]) j++;
}
while(i+1 < n && nums[i] == nums[i+1]) i++;
}
return output;
}
};