文档章节

Leetcode——3Sum

wikison
 wikison
发布于 2015/09/18 17:27
字数 608
阅读 58
收藏 1

原题如下:

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:

  • 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)

这道题让我想起了Leetcode的第一道题,即2Sum。很多人跟我说这两道题很像,但是我做完之后感觉一点都不像。

在2Sum这道题里面,Leetcode对时间的要求很高,所以用的是hash table的思想来解决的,即把value为key,position作为value,如果有冲突的话可以在一个bucket里放多个value。这样的话复杂度就只有O(n)。

3Sum不一样,是确定一个值之后来确定另外两个值。确定另外两个值复杂度最低也是O(n),所以总体的复杂度是O(n^n)。

仔细观察题目,第一个要求是要将数组以增序输出,所以我们最好将整个数组排序,复杂度为O(n^n),最低为O(nlogn)(使用快排)。排序对后面的扫描是相当有用的。

第二个要求是不能重复。初看上去挺难的,其实很简单,只需要在扫描的过程中跳过重复的既可。

代码如下,思路比较简单:

class Solution
{
public:
    vector< vector<int> > threeSum(vector<int>& nums)
    {
        vector< vector<int> > result;
        result.clear();
        unsigned int i;
        unsigned int j;
        unsigned int k;
        int sum;
        if (nums.size() < 3)
        {
            return result;
        }

        bubble_sort(nums);  //首先进行从小到大排序
        i = 0;
        while (i < nums.size() - 2)
        {
            j = i + 1;
            k = nums.size() - 1;
            while (j < k)
            {
                sum = nums[i] + nums[j] + nums[k];
                if (0 == sum)   //和为0时,需要去除那些重复的数字
                {
                    vector<int> triplet;
                    triplet.push_back(nums[i]);
                    triplet.push_back(nums[j]);
                    triplet.push_back(nums[k]);
                    result.push_back(triplet);
                    //去除重复
                    while (j < k && nums[j] == triplet[1]) j++;     //去重又自增,这个循环总会执行至少一遍
                    while (j < k && nums[k] == triplet[2]) k--;
                }
                else if (sum > 0)   //和大于0,k必须向左移动降低组合的值
                {
                    k--;
                }
                else
                {
                    j++;
                }
            }

            int temp = nums[i];
            while (i < nums.size() - 2 && nums[i] == temp) i++;
        }
        return result;
    }

private:
    void bubble_sort(vector<int>& nums) //冒泡排序
    {
        bool is_swap;

        for (unsigned int i = nums.size() - 1; i > 0; i--)
        {
            is_swap = false;
            for (unsigned int j = 0; j < i; j++)
            {
                if (nums[j] > nums[j+1])
                {
                    swap(nums[j], nums[j+1]);
                    is_swap = true;
                }
            }
            if (false == is_swap)
            {
                break;
            }
        }
    }

    void swap(int& a, int& b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
};

参考文章:

http://blog.csdn.net/zhouworld16/article/details/16917071

http://blog.csdn.net/nanjunxiao/article/details/12524405

© 著作权归作者所有

共有 人打赏支持
wikison
粉丝 1
博文 23
码字总数 11471
作品 0
闵行
私信 提问
Leetcode_Problem 16_3 Sum Closest

题目 问题网址: https://leetcode.com/problems/3sum-closest/description/ 问题描述: Given an array S of n integers, find three integers in S such that the sum is closest to a giv......

quiet_girl
2018/03/09
0
0
923. 3Sum With Multiplicity - LeetCode

Question 923. 3Sum With Multiplicity Solution 题目大意: 给一个int数组A和一个目标值target,求满足下面两个条件的组合个数,其中i,j,k分别为数组的索引 i target = A[i] + A[j] + A[k] 思...

yysue
2018/10/22
0
0
nomasp 博客导读:Lisp/Emacs、Algorithm、Android

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/44966625 Profile Introduction to Blog 您能看到这篇博客导读...

nomasp
2015/09/17
0
0
LeetCode日记2

LeetCode-5 思路: (1)最后用子字符串操作返回string。 return s.substr(startpos, maxlength); (2)回文串的判断: 1)首先找出回文串中间连续的重复的字符。 2)再向两边进行判断 (3...

fxdhdu
2015/10/19
53
0
Leetcode之15. 3Sum (medium)

15. 3Sum (medium) 描述 Given an array of n integers, are there elements a, b, c in such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. No......

wxiaoqi
2018/10/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

equals()的重写规则

自反性。对于任何非null的引用值x,x.equals(x)应返回true。 对称性。对于任何非null的引用值x与y,当且仅当:y.equals(x)返回true时,x.equals(y)才返回true。 传递性。对于任何非null的引用...

无精疯
20分钟前
2
0
Go基础系列:双层channel用法示例

双层通道的解释见Go的双层通道 以下是一个双层通道的使用示例。注意下面的示例中使用了"信号通道"(Signal channel),但这里的信号通道是多余的,仅仅只是为了介绍。 信号通道不用来传递数据,...

echojson
28分钟前
1
0
PHP文件上传error的错误类型

PHP文件上传error的错误类型 - $_FILES['file']['error'] 有以下几种类型 1、UPLOAD_ERR_OK 其值为 0,没有错误发生,文件上传成功。 2、UPLOAD_ERR_INI_SIZE 其值为 1,上传的文件超过了 ph......

小良下山化了个缘
54分钟前
2
0
分布式项目(四)Mapping Server 数据映射

上回说道CoAp client和server的实现,数据也安装定义的格式发送到了kafka中,接下来就是Mapping server的实现,物理设备数据映射到抽象设备上,并赋予数据业务含义。 iot-mapping 构建iot-m...

lelinked
今天
3
0
使用data pump驱动的外部表移动数据

使用data pump驱动的外部表移动数据 比如我们有一个报表的数据,准备从一个数据库A中移动到另一个数据库B中,如何实现? 这个问题,我们使用带data pump驱动的外部表方式,很容易实现,具体方法如下...

突突突酱
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部