原題
Description
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.
Notice
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.
Example
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:
(-1, 0, 1)
(-1, -1, 2
解題
題意是，從一組中悬包，找到三個數(shù)鉴分，要求這三個數(shù)加起來為0建丧，找到所有這樣的組合。
最樸素的思想是直接進(jìn)行三重循環(huán)叭首，時間復(fù)雜度為O(n^3)。
有一個較為簡單的問題是2Sum，即從一組數(shù)中找到兩個數(shù)龄坪，使得兩個數(shù)加起來為0。這道題中复唤，我們可以先固定一個數(shù)健田，那么這個問題就退化為2Sum。具體做法為：
首先將數(shù)組排序佛纫，然后從遍歷數(shù)組中的每一位數(shù)妓局，將此數(shù)作為三個數(shù)中的第一個數(shù)总放，然后再這個數(shù)的右邊尋找兩個數(shù)，使得這三個數(shù)和為0好爬。這兩個數(shù)的尋找過程可以參考2Sum局雄，即使用兩個指針分別指向數(shù)組的首尾，然后向中間靠近存炮。
代碼
class Solution {
public:
/*
* @param numbers: Give an array numbers of n integer
* @return: Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int>> threeSum(vector<int> &numbers) {
// write your code here
vector<vector<int>> ans;
sort(numbers.begin(), numbers.end());
auto it = numbers.begin();
while (it != numbers.end()) {
if (*it > 0) break;
if (it != numbers.begin() && *it == *(it - 1)) {
it++; continue;
}
auto nega = it + 1;
auto posi = numbers.end() - 1;
while (nega < posi) {
int sum = *nega + *posi + *it;
if (sum == 0) {
ans.push_back(vector<int>{*it, *nega, *posi});
posi--;
while (*posi == *(posi + 1)) posi--;
nega++;
while (*nega == *(nega - 1)) nega++;
} else if (sum > 0) {
posi--;
} else {
nega++;
}
}
it++;
}
return ans;
}
};
