//

// Solution15.cpp

// Algorithm

//

// Created by Pancf on 2020/10/11.

// Copyright © 2020 Pancf. All rights reserved.

//

#include "Solution15.hpp"

#include <algorithm>

std::vector<std::vector<int>> Solution15::threeSum(std::vector<int>& nums)

{

std::vector<std::vector<int>> res;

if (nums.size() < 3) return res;

std::sort(nums.begin(), nums.end());

for (int i = 0; i < nums.size() - 2 && nums[i] <= 0; ++i) {

int sum = 0 - nums[i];

int low = i + 1;

int high = nums.size() - 1;

while (low < high) {

if (sum == nums[low] + nums[high]) {

res.push_back({nums[i], nums[low], nums[high]});

while (low < high && nums[low] == nums[low + 1]) ++low;

while (low < high && nums[high] == nums[high - 1]) --high;

++low;

--high;

} else if (sum > nums[low] + nums[high]) {

++low;

} else {

--high;

}

}

while (nums[i] == nums[i + 1] && i < nums.size() - 2) ++i;

}

return res;

}