15. 3Sum.txt

//Имеется массив с числами. Нужно найти все триплеты ([nums[i], nums[j], nums[k]) сумма которых = 0. Цифры в триплетах не должны повторяться(Даже так{3,1,2},{3,2,1}). 
//Простой перебор не поможет, т.к. возикнут случаи дублирования триплета, поскольку в массиве могут иметься несколько одинаковых значений.
//Сначала сортируем массив по возрастанию. Теперь все одинковые значения окажутся рядом, и мы сможем их пропустить.
//Объявляем цикл. Если текущее значение массива = предыдущему, то пропускаем его (Исключая 1ое).
//Выбераем самое левое число как первое значение триплета. Остальные два значения задаём левой и правой границей.(Левая граница = первому значению + 1).
//Если сумма триплета > 0, то уменьшаем правую границу на -1, если сумма < 0, то увеличиваем левую границу на + 1. Продолжаем пока границы на сравняются.
//Если сумма = 0 добавляем её в массив ответа. Затем смещаем левую границу на + 1 для продолжения цикла. Если текущее значение границы совпадает с предыдущим, то пропускаем его.  


class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> answer;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int leftBorder = i + 1, rightBorder = nums.size() - 1;
            while (leftBorder < rightBorder)
            {
                int sum = nums[i] + nums[leftBorder] + nums[rightBorder];
                if (sum > 0)
                    rightBorder--;
                else if (sum < 0)
                    leftBorder++;
                else
                {
                    vector<int> temp = {nums[i] , nums[leftBorder], nums[rightBorder]};
                    answer.push_back(temp);
                    leftBorder++;
                    while(nums[leftBorder] == nums[leftBorder - 1] && leftBorder < rightBorder)
                        leftBorder++;
                }
            }
        }
        return answer;
    }
};