Задача: 18. 4Sum
Сложность: medium

Дан массив nums из n целых чисел и целое число target.
Найди все уникальные четверки чисел [nums[a], nums[b], nums[c], nums[d]], такие что сумма равна target, а индексы — различные.

Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

👨‍💻 Алгоритм:

1⃣Отсортируй массив nums, чтобы можно было применять метод двух указателей.

2⃣Зафиксируй два элемента (a, b) с помощью вложенных циклов, и для оставшихся двух (c, d) используй два указателя.

3⃣Подбирай четверки, сумма которых равна target, и добавляй их в результат, проверяя на уникальность.

😎 Решение:

class Solution { 
public: 
    vector<vector<int>> fourSum(vector<int>& nums, int target) { 
        int n = nums.size(); 
        vector<vector<int>> ans; 
        sort(nums.begin(), nums.end()); 
 
        for (int a = 0; a < n; a++) { 
            for (int b = a + 1; b < n; b++) { 
                int c = b + 1; 
                int d = n - 1; 
                while (c < d) { 
                    long long sum = nums[a]; 
                    sum += nums[b]; 
                    sum += nums[c]; 
                    sum += nums[d]; 
                    if (sum < target) { 
                        c++; 
                    } else if (sum > target) { 
                        d--; 
                    } else { 
                        vector<int> v = {nums[a], nums[b], nums[c], nums[d]}; 
                        if (find(ans.begin(), ans.end(), v) == ans.end()) { 
                            ans.push_back(v); 
                        } 
                        c++; 
                        d--; 
                    } 
                } 
            } 
        } 
        return ans; 
    } 
};

Ставь 👍 и забирай 📚 Базу знаний