[LeetCode]3Sum

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

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下的解决方案,套用了其标题(不知道怎么翻译)。这种方式只需要两层的循环,即可算出符合预期的结果集。

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

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;
    }
};

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


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

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


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。