文档章节

每天AC系列(四):四数之和

氷泠
 氷泠
发布于 01/26 13:03
字数 1555
阅读 94
收藏 0

1 题目

Leetcode第18题,给定一个数组与一个target,找出数组中的四个数之和为target的不重复的所有四个数. 在这里插入图片描述

2 暴力

List<List<Integer>> result = new ArrayList<>();
if (nums.length == 4 && nums[0] + nums[1] + nums[2] + nums[3] == target)
    result.add(Arrays.asList(nums[0], nums[1], nums[2],nums[3]));
else if (nums.length > 4) 
{
    Arrays.sort(nums);
    Set<List<Integer>> resultSet = new HashSet<>();
    for(int i=0;i<nums.length-3;++i)
    {
        for(int j=i+1;j<nums.length-2;++j)
        {
            for(int k=j+1;k<nums.length-1;++k)
            {
                for(int m=k+1;m<nums.length;++m)
                {
                    if(nums[i]+nums[j]+nums[k]+nums[m] == target)
                        resultSet.add(Arrays.asList(nums[i],nums[j],nums[k],nums[m]));
                }
            }
        }
    }
    result.addAll(resultSet);
    Collections.sort(result,(t1,t2)->
    {
        if(t1.get(0) > t2.get(0))
            return 1;
        if (t1.get(0) < t2.get(0))
            return -1;
        if (t1.get(1) > t2.get(1))
            return 1;
        if (t1.get(1) < t2.get(1))
            return -1;
        if (t1.get(2) > t2.get(2))
            return 1;
        if (t1.get(2) < t2.get(2))
            return -1;
        if (t1.get(3) > t2.get(3))
            return 1;
        if (t1.get(3) < t2.get(3))
            return -1;
        return 0;
    });
}
return result;

判断长度,然后排序,直接上四个for,然后... 在这里插入图片描述 好! 惨败.

3 优化

3.1 去掉结果排序

首先最后的排序是不必要的,也就是后面的

Collections.sort(result,(t1,t2)->
{
    if(t1.get(0) > t2.get(0))
        return 1;
    if (t1.get(0) < t2.get(0))
        return -1;
    if (t1.get(1) > t2.get(1))
        return 1;
    if (t1.get(1) < t2.get(1))
        return -1;
    if (t1.get(2) > t2.get(2))
        return 1;
    if (t1.get(2) < t2.get(2))
        return -1;
    if (t1.get(3) > t2.get(3))
        return 1;
    if (t1.get(3) < t2.get(3))
        return -1;
    return 0;
});

对结果进行排序不必要,虽然会在测试时与答案有差别,但是提交的话不需要排序.

3.2 stream去重

之前的操作用的是HashSet进行去重,有一个符合的四元组就直接添加进集合中,现在采用了stream+distinct去重:

return result.stream().distinct().collect(Collectors.toList());

3.3 双指针+最大最小剪枝

可以利用类似三数之和的思想,固定一个数,双指针分别指向两端的两个数,这里的话,四个数,选择固定两个数,计算它们的和并把它们看作一个数,即可利用双指针.

for(int i=0;i<nums.length-3;++i)
{
     for(int j=i+1;j<nums.length-2;++j)
     {
         int m = nums[i] + nums[j];
         int left = j+1;
         int right = nums.length-1;
         while(left < right)
         {
             int temp = m + nums[left] + nums[right];
             if(temp == target)
             {
                 result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                 --right;
                 ++left;
             }
             else if(temp > target)
                 --right;
             else
                 ++left;
         }
     }
 }

m为固定的数,left与right就是双指针,根据"三数"之和判断与目标值的大小移动双指针. 最小剪枝就是首先计算"三数"的最小值,若大于目标值就可以跳过,最大剪枝就是计算"三数"的最大值,若小于目标值则跳过,进入下一个循环:

int m = nums[i] + nums[j];
int left = j+1;
int right = nums.length-1;
if(m + nums[left] + nums[left+1] > target)
    continue;
if (m + nums[right-1] + nums[right] < target)
    continue;

3.4 提交

在这里插入图片描述

呃...好了那么一点点吧.

4 来来来再快一点

4.1 初始判断

首先,初始的判断可以再简单一点,如果数组为空或长度小于4,直接返回.

List<List<Integer>> result = new ArrayList<>();
if (nums == null && nums.length < 4)
	return result;

4.2 一次不够,就再剪几次

上面的算法中,只是在两层for里面进行了一次最大最小剪枝,可以在没进入for之前剪一次:

Arrays.sort(nums);
int len = nums.length;
if(
	nums[0] + nums[1] + nums[2] + nums[3] >  target 
	|| 
	nums[len-4] + nums[len-3] + nums[len-2] + nums[len-1] < target
)
    return result;
for(int i=0;i<len-3;++i)   

注意要先排序,然后直接判断整个数组的最大最小值并与target判断. 然后在进入第一层for之后再剪一次:

for(int i=0;i<len-3;++i)
{
	if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target)
		break;
    if(nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target)
		continue;
    for(int j=i+1;j<len-2;++j)
}

因为数组是升序排序的,因此,"最左边"四个数肯定是最小值,若这个最小值大于target,可以直接break了,但是,最右边三个数与nums[i]相加不一定为最大值,因此判断之后若小于target只能continue.

4.3 去重

4.3.1 双指针去重

首先,在双指针的循环中,若发现了有四个数符合条件,可以尝试多次移动指针:

result.add(Arrays.asList(nums[i], nums[j], nums[left++], nums[right--]));
while(left < right && nums[left] == nums[left-1])
    ++left;
while(left < right && nums[right] == nums[right+1]) 
    --right;

因为值一样的可以一次性移动指针,不需要再次进行和的判断. 呃,可以尝试提交了.

在这里插入图片描述

咦,不对啊,做了这么多,没快多少啊... 为啥呢... ...

4.3.2 外循环去重

找了很久,发现是这里的原因:

return result.stream().distinct().collect(Collectors.toList());

这里去重的话,用是用的很舒服,一个stream(),一个distinct()就好了,问题是...还是很慢啊!!! 所以呢,需要手动去重,出现重复的原因就是数组中有重复的数,比如:

[1,1,1,1,2,2,2,2],target=6

顺序判断时,会好几个

[1,1,2,2]

因此,对于重复的数,进行跳过处理,在第一层for中,对重复过的进行跳过:

for(int i=0;i<len-2;++i)
	if(i>0 && nums[i] == nums[i-1]) continue;

其次,在第二层for中,也对重复过的进行跳过:

for(int j=i+1;j<len-2;++j)
	if(j > i+1 && nums[j] == nums[j-1]) continue;

这样的话,例如对于上面的(不同的1用字母区分)

[1(a),1(b),1(c),1(d),2,2,2,2]

一开始是a处的1与b处的1,然后到了第二层循环,因为此时j=i+1,指向b处的1,因此不会跳过1,会进入双指针循环,第二次j指向c处的1,出现重复,j不断跳过直到j指向2.然后2结束后,到了i这层循环,因为1出现过,i不断跳过直到i指向2.

没错,说了这么多,去重不需要什么HashSet,不需要什么stream,只需两行:

if(i>0 && nums[i] == nums[i-1]) continue;
if(j>i + 1 && nums[j] == nums[j-1]) continue;

4.4 提交

在这里插入图片描述

尽力了.

5 源码

github

码云

© 著作权归作者所有

氷泠
粉丝 0
博文 61
码字总数 84933
作品 0
广州
私信 提问
加载中

评论(0)

Leetcode【279、343】

问题描述:【BFS、Math】279. Perfect Squares 解题思路: 这道题是给一个正整数 n,将其分解为平方数加法因子,使得分解后的因子最少。 这道题实际上和 Leetcode 【DP、BFS】322. Coin Cha...

牛奶芝麻
2019/07/20
0
0
12.1 省选训练总结2(1) 点分治/平衡树

目录 点分治 Splay 完成情况截图 聪聪可可 普通平衡树 文艺平衡树 宠物收养所 Cards Sorting 点分治 首先找重心,然后对过了重心的路径计算,最后递归点分。 前4道题是点分裸题,就不赘述。 ...

OwenOwl
2017/12/01
0
0
Python3 欧拉计划 问题1-5

欧拉计划(Project Euler)是一个解题网站,包括一系列有挑战性的数学与计算机编程题;要解开它们,需要的不止是数学知识:尽管数学能够帮助你找到一些优雅而有效的方法,大多数题目仍需要借...

AiFan
2017/11/06
0
0
LeetCode 15. 3Sum(三数之和)

原题 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The ......

dby_freedom
2018/09/11
0
0
SDL系列讲解(十) 按键处理流程

SDL系列讲解(一) 简介 SDL系列讲解(二) 环境搭建 SDL系列讲解(三) 工具安装 SDL是什么,能干什么,为什么我们要学习它? SDL系列讲解(四) demo讲解 SDL系列讲解(五) 调试c代码 SD...

代码GG陆晓明
2017/10/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

天津哪里可以开建材发票-腾讯新闻网

天津哪里可以开建材发票【152 * 9б 28 * 21 б9】陈生,诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug Bridge,...

16534163966
刚刚
0
0
北京哪里可以开海关缴款书发票-腾讯新闻网

北京哪里可以开海关缴款书发票【152 * 9б 28 * 21 б9】陈生,诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug B...

15983684413
1分钟前
5
0
北京哪里可以开粮油发票-腾讯新闻网

北京哪里可以开粮油发票【152 * 9б 28 * 21 б9】陈生,诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug Bridge,...

16534163727
3分钟前
15
0
北京哪里可以开文化传播发票-腾讯新闻网

北京哪里可以开文化传播发票【152 * 9б 28 * 21 б9】陈生,诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug Bri...

17035270196
4分钟前
3
0
北京哪里可以开电线电缆发票-腾讯新闻网

北京哪里可以开电线电缆发票【152 * 9б 28 * 21 б9】陈生,诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug Bri...

15232501104
5分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部