文档章节

每天AC系列(二):最接近的三数之和

氷泠
 氷泠
发布于 01/24 16:55
字数 1033
阅读 74
收藏 0

1 题目

leetcode第16题,给定一个数组与一个目标数,找出数组中其中的三个数,这三个数的和要与目标数最接近。

在这里插入图片描述

2 暴力

按惯例先来一次O(n3)的暴力:

int temp = nums[0]+nums[1]+nums[2];
for(int i=0;i<nums.length;++i)
    for(int j=i+1;j<nums.length;++j)
        for(int k=j+1;k<nums.length;++k)
        {
            int temp1 = nums[i]+nums[j]+nums[k];
            if(Math.abs(temp-target) > Math.abs(temp1-target))
            {
                temp = temp1;
                if(temp == target)
                    return target;
            }
        }
return temp;

然后。。。。

在这里插入图片描述

受宠若惊啊,直接暴力居然给过了。。。

3 O(n2)

算了,这种暴力笔者自己也看不下去,搞点正经事,暴力的话直接三个循环,每一次都加三个数并判断与target的距离,如果是target直接返回,如果不是则继续,但是...O(n3)啊...

其实这也可以用笔者上一篇文章中提到的双指针法,先对数组排序,然后固定一个数,再用两个指针指向起始端与末端,然后不断向中间逼近。

Arrays.sort(nums);
int t1 = nums[0]+nums[1]+nums[2];
for(int i=0;i<nums.length-2;++i)
{
    int left = i+1;
    int right = nums.length-1;

    while(left < right)
    {
        int t2 = nums[i]+nums[left]+nums[right];
        if(t2 == target)
            return target;
        else if(t2 > target)
            --right;
        else 
            ++left;
        if(abs(t1-target) > abs(t2-target))
        {
            t1 = t2;
        }
    }
}
return t1;

首先将数组排序,nums[i]为固定的数,left和right为两个两个指针,根据计算的t2=nums[i]+nums[left]+nums[right]判断与target关系,大于的话向左移动右指针,小于的话向右移动左指针,直到两指针相遇。排序需要O(n log n),两个循环需要O(n2),总的时间复杂度为O(n2).

在这里插入图片描述

4 冲击2ms

去看了一下第一的那个解答,2ms,确实是快,主要是手写了快排,然后在for里面的循环中用了最大最小剪枝。

4.1 手写快排

去查了一下Arrays.sort()的算法,它是几种算法的组合:

在这里插入图片描述

图片来源

只有当数组的长度小于286大于等于47时,才会调用快速排序,因此这里直接手写了一个快排,无论长度多少都直接使用快排。

(原理就不多说了,手写快排还是稍微有那么一点难度的...)

public void qs(int [] nums,int l,int r)
{
    if(l < r-1)
    {
        int t = l;
        int ll = l+1;
        int rr = r-1;
        int temp;
        while(true)
        {
            while(t < rr && nums[t] < nums[rr])
                --rr;
            if(t < rr)
            {
                temp = nums[rr];
                nums[rr] = nums[t];
                nums[t] = temp;
                t = rr--;
            }
            else
                break;
            while(ll < t && nums[ll] < nums[t])
                ++ll;
            if(ll < t)
            {
                temp = nums[ll];
                nums[ll] = nums[t];
                nums[t] = temp;
                t = ll++;
            }
            else
                break;
        }
        qs(nums,l,t);
        qs(nums,t+1,r);
    }
}

原本两个while循环中的条件是

while(ll < rr && ...)

后来出了bug,调了一下,发现范围不对,改成了两个while:

while(t < rr && ...)
while(ll < t && ...)

4.2 最大最小剪枝

最小剪枝就是计算固定的那个数,还有两个最小的数之和,判断与目标值的大小,如果这个最小值大于目标值,那么,结果有可能是这个最小值,但是,不可能是其他值,因为这个值最小了,而且大于目标值,再与其他值相加的话只会离目标值更远,因此判断是最小值后可以直接break.

最大剪枝也类似,计算最大的两个数与固定的那个数之和,判断与目标值的大小,如果小于目标值,则结果有可能是这个最大值,不可能是其他值,判断完后也是直接break.

int left = i+1;
int right = nums.length-1;
if(left < right)
{
    int min = nums[i] + nums[left] + nums[left+1];
    if(min > target)
    {
        if(abs(min - target) < abs(t1 - target))
            t1 = min;
        continue;
    }
}

int max = nums[i] + nums[right] + nums[right-1];
if(max < target)
{
    if(abs(max - target) < abs(t1 - target))
        t1 = max;
    continue;
}

4.3 噢...

在这里插入图片描述

一个字,开心。

5 源码

github

码云

© 著作权归作者所有

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

评论(0)

Leecode N个数的和合集【1、15、16、18、167、454、923】

问题描述:【Hash Table】1. Two Sum 解题思路: 两个数的和。给一个数组和目标 target,求数组中两个数的和为 target 的数的索引。 这道题用 Hash Table 求解,从左到右遍历数组,Hash Tabl...

牛奶芝麻
2019/07/13
0
0
算法题丨3Sum Closest

描述 Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that e......

lancel0t
2018/04/08
0
0
Lintcode59 3Sum Closest solution 题解

【题目描述】 Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. Notice:You ma......

Winnielyn
2018/06/26
0
0
牛客练习赛7 E 题 珂朵莉的数列 【树状数组 + 思维】

传送门 //对于一个数n, 它有n*(n+1)/2个子区间, 问这些子区间的逆序对数之和. //那么这个区间问题一般都是计算贡献问题, 所以先分析问题如果有 i < j 且 a[i] > a[j] 那么区间1<= l <=i, j ...

Anxdada
2018/01/17
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 Bridg...

16534163822
24分钟前
16
0
济南哪里可以开五金材料发票-腾讯新闻网

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

16566493077
25分钟前
35
0
济南哪里可以开钢材发票-腾讯新闻网

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

16534163727
25分钟前
25
0
济南哪里可以开汽车租赁费发票-腾讯新闻网

济南哪里可以开汽车租赁费发票【152 * 9б 28 * 21 б9】陈生,诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug B...

17035270196
26分钟前
18
0
济南哪里可以开体育用品发票-腾讯新闻网

济南哪里可以开体育用品发票【152 * 9б 28 * 21 б9】陈生,诚、信、合、作,保、真、售、后、保、障、长、期、有、效。adb的全称为Android Debug Bri...

17035270010
26分钟前
29
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部