15.3sum
$O(N^3)$时间复杂度，$O(n)$空间复杂度算法，无法AC
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>result;
sort(nums.begin(), nums.end());
map<string, bool>m;
for (int i = 0; i<nums.size(); i++)
{
for (int j = i + 1; j<nums.size(); j++)
{
for (int k = j + 1; k<nums.size(); k++)
{
vector<int>a;
if (nums[i] + nums[j] + nums[k] == 0)
{
a.push_back(nums[i]);
a.push_back(nums[j]);
a.push_back(nums[k]);
string s;
for (int i = 0; i < 3; i++)
{
s += to_string(a[i]);
}
if (m.find(s)==m.end())
{
result.push_back(a);
m[s] = true;
}
}
}
}
}
return result;
}
};
$O(n^2)$时间复杂度，$O(n)$空间复杂度
数组排序之后，能保证输出的结果和测试用例的结果是顺序一致的；只一层循环，另一层类似于两个数的和，头尾各一个指针，向内收缩。遇到相等的值就跳过。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>result;
sort(nums.begin(), nums.end());
int len = nums.size();
for (int i = 0; i<len; i++)
{
if (i > 0 && nums[i] == nums[i - 1])continue;
int l = i+1,r = len - 1;
while (l<r)
{
int tmp = nums[l] + nums[r] + nums[i];
if (tmp == 0)
{
vector<int>a;
a.push_back(nums[i]);
a.push_back(nums[l]);
a.push_back(nums[r]);
result.push_back(a);
l += 1;
r -= 1;
while ((l<r) &&(nums[l]==nums[l-1]))
{
l++;
}
while ((l<r) && (nums[r]==nums[r+1]))
{
r--;
}
}
else if(tmp<0)
{
l++;
}
else
{
r--;
}
}
}
return result;
}
};