原题

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

Note: 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]
]

题解

暴力解法

因为需要计算三个数字的总和,所以需要进行3层的遍历,故时间复杂度需要O(n^3),看来不可取,果断放弃。毕竟是medium难度的题,不至于这么个解法。

two-pointes solution

在解决问题后,简单看了下Discuss下的解决方案,套用了其标题(不知道怎么翻译)。这种方式只需要两层的循环,即可算出符合预期的结果集。

但是在遍历之前,需要对原始数组进行一次排序,为了更容易使结果集去重。

[code lang=”cpp”]
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector< vector<int> > rs;
int l = nums.size();
sort(nums.begin(), nums.end());

for (int i = 0; i < l – 2; ++i) {
int f = i + 1, b = l – 1;
if (i – 1 >= 0 && nums[i] == nums[i – 1]) continue;
while (f < b) { if (nums[f] + nums[b] > -nums[i]) {
while(nums[b] == nums[–b]) {}
} else if (nums[f] + nums[b] < -nums[i]) {
while(nums[f] == nums[++f]) {}
} else {
vector<int> tmp = {nums[i], nums[f], nums[b]};
rs.push_back(tmp);
while(nums[b] == nums[–b]) {}
while(nums[f] == nums[++f]) {}
}
}
}

return rs;
}
};
[/code]

时间复杂度:O(n^2)
空间复杂度:O(n)


原题:https://leetcode.com/problems/3sum

文章来源:胡小旭 => [LeetCode]3Sum

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.