15. 3Sum

Задание.

Дан целочисленный массив nums

Нужно вернуть все триплеты [nums[i], nums[j], nums[k]] такие, что i != j, i != k и j != k, и nums[i] + nums[j] + nums[k] == 0.

Обратите внимание, что набор решений не должен содержать повторяющихся триплетов.

Пример 1.

Входные данные: nums = [-1,0,1,2,-1,-4]

Результат: [[-1,-1,2],[-1,0,1]]

Пояснение:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

Различными триплетами являются [-1,0,1] и [-1,-1,2]. Обратите внимание, что порядок вывода и порядок триплетов не имеет значения.

Пример 2.

Входные данные: nums = [0,1,1]

Результат: []

Пояснение: Единственный возможный триплет не суммируется до 0.

Пример 3.

Входные данные: nums = [0,0,0]

Результат: [0,0,0]

Пояснение: Единственный возможный триплет суммируется до 0.

Решение.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int target = 0, i, j, k, sum;
        set<vector<int>> s;

        std::sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++){
            j = i + 1;
            k = nums.size() - 1;
            while (j < k) {
                if ((sum = nums[i] + nums[j] + nums[k]) == target) {
                    s.insert({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }

        vector<vector<int>> output;
        for(auto triplets : s)
            output.push_back(triplets);

        return output;       
    }
};