LeetCode-15-3Sum&&4Sum

15. 3Sum

Given an array S of n integers, are there elements a, b, c 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]
]

同之前的2sum差不多,计算两个的和的方式是:为了避免重复,重新用一个set容器,解决重复的问题。但是这里的情况是,重复的一个数字是可以出现的,而且是三个数字相加的和,所以我们没法用之前的处理办法。

很容易想到的办法是,先让一个指针向前走,然后对之后的数字搜索,为了减少搜索的复杂度,我们可以先将数组进行排序,先排序后搜索,可以从O(n^2)的复杂度减小到nlog(n),所以采用先排序。

然而这里需要注意的是,需要判断数组中有相同数字的情况。虽然结果中允许有相同的数字出现,但不允许出现完全相同的两个结果,所以需要处理这种情况。 具体的代码如下:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size()<=0)
            return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()&&nums[i]<=0;++i){
            int j=i+1,k=nums.size()-1;
            while(j<k){
                    if(nums[i]+nums[j]+nums[k]<0)
                        j++;
                    else if(nums[i]+nums[j]+nums[k]>0)
                        --k;
                    else if(nums[i]+nums[j]+nums[k]==0){
                        vector<int> temp(3,0);
                        temp[0]=nums[i];
                        temp[1]=nums[j];
                        temp[2]=nums[k];
                        res.push_back(temp);
                        while(k>j&&nums[k]==temp[2]) //去除k的重复
                            k--;
                        while(k>j&&nums[j]==temp[1]) //去除j的重复
                            j++;
                    }
                }
                while(i+1<nums.size()&&nums[i+1]==nums[i])  //去除i的重复
                    i++;
            }
        return res;
    }
};

18. 4Sum

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 : The solution set must not contain duplicate quadruplets.

其实跟前面的3sum解决的办法是一样的,无非这里为了减少一点复杂度,借用了一下大家使用的方法。,在每次遍历的时候进行一点判断,以减少循环的次数。代码如下:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n=nums.size();
        if(n<4)
            return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;++i){
            if(i>0&&nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if(nums[i]+nums[n-1]+nums[n-2]+nums[n-3]<target) continue;
            for(int j=i+1;j<nums.size()-2;++j){
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                int begin=j+1,end=n-1;
                while(begin<end){
                    int sum=nums[i]+nums[j]+nums[begin]+nums[end];
                    if(sum>target)
                        --end;
                    else if(sum<target)
                        ++begin;
                    if(sum==target){
                        vector<int> temp(4,0);
                        temp[0]=nums[i];
                        temp[1]=nums[j];
                        temp[2]=nums[begin];
                        temp[3]=nums[end];
                        res.push_back(temp);
                        while(begin<end&&temp[2]==nums[begin])
                            ++begin;
                        while(begin<end&&temp[3]==nums[end])
                            --end;
                    }
                }
            }
        }
         return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hongten

算法入门-插入排序算法

9140
来自专栏数据结构与算法

P3805 【模版】manacher算法

题目描述 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 字符串长度为n 输入输出格式 输入格式: 一行小写英文字符a,...

33960
来自专栏Android机动车

RxJava从入门到不离不弃(三)——转换操作符

所有这些Operators都作用于一个可观测序列,然后变换它发射的值,最后用一种新的形式返回它们。概念实在是不好理解,下面我们结合实际的例子一一介绍。

8630
来自专栏Java 源码分析

二叉搜索树

一、操作: 判断元素是否存在:递归的在左右子树中查找 查找最小元素:在左子树中递归或者循环 查找最大元素:在右子树中递归或循环 插入:递归的插入,大于则插入在节...

30350
来自专栏猿人谷

对称字符串的最大长度

题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。 思路...

25580
来自专栏ShaoYL

OC正则表达式的简单使用

371130
来自专栏Java开发者杂谈

算法之逆序对

算法之逆序对 逆序对问题 ​ 假设A[1..n]是一个有n个不同数的数组。若iA[j],则对偶(i, j)称为A的一个逆序对(inversion)。 列出数组{...

37790
来自专栏软件工程师成长笔记

Map集合按照ASCII码从小到大(字典序)排序--JAVA

1K20
来自专栏Felix的技术分享

C++与汇编小结

41040
来自专栏互联网开发者交流社区

正则表达式-基础使用整理

10130

扫码关注云+社区

领取腾讯云代金券