給定一個(gè)有 n 個(gè)整數(shù)的數(shù)組 S,是否存在三個(gè)元素 a,b,c 使得 a+b+c=0? 找出該數(shù)組中所有不重復(fù)的 3 個(gè)數(shù),它們的和為 0。
備注:
這三個(gè)元素必須是從小到大進(jìn)行排序。
結(jié)果中不能有重復(fù)的 3 個(gè)數(shù)。
例如,給定數(shù)組 S={-1 0 1 2 -1 4},一個(gè)結(jié)果集為:
(-1, 0, 1)
(-1, -1, 2)
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)
經(jīng)典方法,可惜我并沒有想到這樣寫……
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int len = nums.size();
for (int current = 0; current < len - 2&&nums[current]<=0;current++)
{
int front = current + 1, back = len - 1;
while (front < back)
{
if (nums[current] + nums[front] + nums[back] < 0)
front++;
else if (nums[current] + nums[front] + nums[back] > 0)
back--;
else
{
vector<int> v(3);
v.push_back(nums[current]);
v.push_back(nums[front]);
v.push_back(nums[back]);
result.push_back(v);
v.clear();
do {
front++;
} while (front < back&&nums[front - 1] == nums[front]);
do {
back--;
} while (front < back&&nums[back + 1] == nums[back]);
}
}
while (current < len - 2 && nums[current + 1] == nums[current])
current++;
}
return result;
}
};
繼續(xù)努力……
和本道題關(guān)聯(lián)密切的題目推薦:
傳送門:LeetCode 16 3Sum Closest(最接近的3個(gè)數(shù)的和)
傳送門:LeetCode 18 4Sum(4個(gè)數(shù)的和)