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)


相关推荐

  • 关于变量在for内部new还是先在循环外定义的一些思考「建议收藏」

    关于变量在for内部new还是先在循环外定义的一些思考「建议收藏」关于变量在for内部new还是先在循环外定义的一些思考

  • windows XP虚拟机安装[通俗易懂]

    windows XP虚拟机安装[通俗易懂]一.安装环境:win10VMware15winxp.iso二.安装过程:1.用自定义(高级)安装(原因是虚拟磁盘类型必须选IDE,而典型是默认磁盘类型的,如果你用典型发现到后面会报错)2.按照自己的需求选择硬件兼容性,建议选择最高的,因为向下兼容。3.插入.iso文件4.选择操作系统和版本5.修改名称和选择安装位置(可默认)6.根据自己的需求修改处理器配置,内存(不得低于1G,即1024MB)、网络类型、I/O控制类型。7.磁盘类型是重点,一定要选择IDE。8.磁盘。

  • live2d模型_判别模型

    live2d模型_判别模型★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号:MindDraft➤博主域名:https://www.zengqiang.org➤GitHub地址:ht

  • java的字符串分割

    java的字符串分割使用split0)方法可以使字符串按指定的分割字符或字符串对内容进行分割,并将分割后的结果存放在字符串数组中。split()方法提供了以下两种字符串分割形式。(1)split(Stringsign)该方法可根据给定的分割符对字符串进行拆分。语法如下:str.spli(Stringsign)其中,sign为分割字符串的分割符,也可以使用正则表达式。.注意:没有统一的对字符进行分割的符号。如果想定义多个分割符,可使用符号“|”。例如,“=”表示分割符分别为“”和“=”。(2)split…

  • acwing-1088旅行问题

    acwing-1088旅行问题原题链接John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 n 个车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),行驶过程中不能出现没有油的情况。任务:判断以每个车站为起点能否按条件成功周游一周。输入格式第一行是一个整数 n,表示环形公路上的车站数;接下来 n 行,每行两个整数

  • docker(6)镜像的使用「建议收藏」

    docker(6)镜像的使用「建议收藏」前言Docker的三大核心概念:镜像、容器、仓库。初学者对镜像和容器往往分不清楚,学过面向对象的应该知道类和实例,这跟面向对象里面的概念很相似我们可以把镜像看作类,把容器看作类实例化后的对象。|

发表回复

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

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