LeetCode18:4Sum

LeetCode18:4Sum

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Given an array S of n integers, are there elements a, b, c, 
and d in S such that a + b + c + d = target? Find all 
unique quadruplets in the array which gives the sum of target.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

这是求四个数的和的问题。能够和前面三个数和的问题一样转化成两个数和的问题。即先固定第一个数。再依据第一个数固定第二个数,然后就是求两数和的问题了。数组里面的元素可能会有反复元素,所以须要注意消除反复的推断。时间复杂度是O(N^3)。

runtime:192ms

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size()<4)
            return result;

        sort(nums.begin(),nums.end());
        vector<int>::iterator iter1=nums.begin();
        vector<int>::iterator iter2=iter1+1;

        //最外层第一个指针遍历
        for(;iter1!=nums.end()-3;iter1++)
        {

            //固定第一个指针后第二个指针遍历
            for(iter2=iter1+1;iter2!=nums.end()-2;iter2++)
            {

                //内层两个指针从两个方向遍历,这是经典的求两个数的和的问题
                int base=*iter1+*iter2;
                vector<int>::iterator iter3=iter2+1;
                vector<int>::iterator iter4=nums.end()-1;
                while(iter3<iter4)
                {
                    if((*iter3+*iter4+base)<target)
                    {
                        iter3++;
                    }
                    else if((*iter3+*iter4+base)>target)
                    {
                        iter4--;
                    }
                    else
                    {
                        //这里须要注意vector中push_back和用下标訪问的差别,用小标訪问时相似于数组,所以tmp初始化时须要指定vector的大小,可是用push_back时不要指定大小。否则小心push_back是在你指定大小的vector后加入元素
                        vector<int> tmp;
                        tmp.push_back(*iter1);
                        tmp.push_back(*iter2);
                        tmp.push_back(*iter3);
                        tmp.push_back(*iter4);
                        result.push_back(tmp);

                        //这是推断是否有反复的方式,假设下一指针依旧小于iter4而且下一个指针指向的值与当前值同样。iter3须要加1
                        while((iter3+1)<iter4 && *(iter3)==*(iter3+1)) iter3++;

                        while(iter3<(iter4-1)&& *(iter4)==*(iter4-1)) iter4--;

                        //推断完毕后还须要将iter3加1或iter4减一以继续查寻下一个和为常数的组合
                        iter3++;
                    }
                }

                //对于iter2也须要推断是否存在反复元素问题
                while(((iter2+1)!=(nums.end()-2))&&(*(iter2)==*(iter2+1))) iter2++;

            }

            //同理对于ier1也是如此
            while(((iter1+1)!=(nums.end()-3))&&(*(iter1)==*(iter1+1))) iter1++;

        }
          return result;   
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116673.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 云服务器ECS和轻云服务器区别

    云服务器ECS和轻云服务器区别

  • StringBuffer源码分析之 append 方法[通俗易懂]

    欢迎点击「算法与编程之美」↑关注我们!本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列博客。StringBuffer这个类是我们日常开发中经常会使用的一个字符串操作类,该类提供了非常多的关于字符串操作相关的类,尤其是append方法更为常用。1目标本次源码分析的目标是深入了解StringBuffer类中append方法的实现机制。2分析方法首先编写测试代码,…

  • tensorflow2.0手写数字识别_python 数字识别

    tensorflow2.0手写数字识别_python 数字识别本文使用Tensorflow框架进行Python编程实现基于卷积神经网络的手写数字识别算法,并将其封装在一个GUI界面中,最终,设计并实现了一个手写数字识别系统。

  • 什么叫侧面指纹识别_前面侧面还是背面?手机指纹识别放哪儿合适

    什么叫侧面指纹识别_前面侧面还是背面?手机指纹识别放哪儿合适自指纹识别功能在智能手机上逐渐被普及之后,被安卓厂商们所抛弃的实体按键又一次回到了手机上。不过与之前不同,这次实体按键并不一定要承载Home键的功能,因此指纹识别的位置也被各个手机厂商玩出了花样,传统一点的将其放在手机的正面,大胆一点的则将指纹识别按键放在机身背面,也有个别厂商为避免前后面板开孔,将指纹识别放在了机身的侧边。那么指纹识别究竟放在哪里更合适呢?目前,在苹果的“号召”下,大部分手机厂商…

  • 五大常用算法之二:动态规划算法

    一、基本概念动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。二、基本思想与策略基本

    2021年12月25日
  • scrapy安装步骤_scrapy安装教程

    scrapy安装步骤_scrapy安装教程Scrapy安装Scrapy的安装有多种方式,它支持Python2.7版本及以上或Python3.3版本及以上。下面说明Python3环境下的安装过程。Scrapy依赖的库比较多,至少需要依赖库有Twisted14.0,lxml3.4,pyOpenSSL0.14。而在不同平台环境又各不相同,所以在安装之前最好确保把一些基本库安装好,尤其是Windows。Anaconda这种…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号