LeetCode(15) 3Sum

时间:2021-10-18 04:31:53

题目

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

分析

求出给定整数序列中三个之和为0的不重复组合序列!

我采用了暴力解决办法,三层循环,但是Status: Time Limit Exceeded~~~

不断思考,得到复杂度为O(n2)的AC代码。

Time Limit Exceeded代码

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> vv; int size = nums.size(); if (size < 3)
return vv; for (int i = 0; i < size; i++)
{
for (int j = i + 1; j < size; j++)
{
for (int k = j + 1; k < size; k++)
{
if (nums[i] + nums[j] + nums[k] == 0)
{
int arr[3] = { nums[i], nums[j], nums[k] };
//将arr中的元素从小到大排序
sort(arr); vector<int> v = { arr, arr + 3 };
if (!find(vv , v))
vv.push_back(v);
}
else{
continue;
}
}//for
}//for
}//for return vv;
} bool find(vector<vector<int>> &vv, vector<int> &v)
{
vector<vector<int>>::iterator iter; for (iter = vv.begin(); iter != vv.end(); iter++)
{
if ((*iter)[0] == v[0] && (*iter)[1] == v[1] && (*iter)[2] == v[2])
{
return true;
}
}
return false;
} void sort(int *a)
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3 - i - 1; j++)
{
if (a[j] > a[j + 1])
{
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}
};

AC代码

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> vv; int size = nums.size(); if (size < 3)
return vv; sort(nums.begin() , nums.end()); for (int i = 0; i < size; i++)
{
//跳过重复数字减少循环
if ((i>0) && nums[i] == nums[i - 1])
continue; int j = i + 1;
int k = size - 1; //如果最大的数还小于0 则直接返回空集合
if (nums[k] < 0)
return vv;
while (j < k)
{
int sum = nums[i] + nums[j] + nums[k]; if (sum == 0)
{
//元素nums[i], nums[j], nums[k]本来就是从小到大排序
int arr[3] = { nums[i], nums[j], nums[k] }; vector<int> v = { arr, arr + 3 }; vv.push_back(v); //跳过重复数字减少循环
while ( (j<k) && (nums[j] == nums[j + 1]))
j++; while ((j<k) && (nums[k] == nums[k - 1]))
k--; j++;
k--;
}
else if(sum < 0){
j++;
}
else{
k--;
}
}
}//for
return vv;
}
};

GitHub测试程序源码