java数据结构与算法刷题-----LeetCode15. 三数之和

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

在这里插入图片描述

解题思路
  1. 和LeetCode1.两数之和一样,但是这道题边界条件更多。
  2. 两数之和那道题目中,我们使用了map进行处理,也讲了如果投机取巧,用大量的数组空间充当map集合,从而达成相同的逻辑处理代码,只是将map换成数组,却比map集合快很多的办法。
  3. 这道题也同样可以用map集合,但是因为边界条件过多,代码十分繁琐,尤其是投机取巧用数组充当hash,确实在做题方面,可以达成超越100%的用户,但是没有任何实际意义,只能做题。(后面也会将代码给出)
  4. 所以这道题,我会给出比较靠谱的办法,时间复杂度也不高,工作中推荐使用。那就是排序+双指针
  5. 先对整个数组排序,然后创建3个指针,从第一个数开始向后枚举
  6. 第一个指针 i 只是起到限定第一个数的作用,我们需要通过双指针left和right,来找到第一个数的右边区域的另外两个数
  7. 初始left左指针指向第一个数 i 的右边第一个位置,而right指向右边区域末尾,如果3个数相加比0大,就说明right指向的数太大,right–即可,反之,如果相加比0小,left就太小了,进行left++。
代码,时间复杂度O(n^2),空间复杂度,数组需要排序,工作场景中,不可以改变原数组,因此需要O(n)空间复杂度来排序。然后排序算法使用快速排序,需要O(logN)的栈空间复杂度。
  1. 方法一:排序+双指针,效率肯定比不过方法二的hash表,而且使用数组当hash表,但是实际工作中,肯定使用方法一。此方法耗时25ms, 方法二耗时0ms
    在这里插入图片描述
class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//先排序,为了双指针枚举提供方便
        List<List<Integer>> ans = new ArrayList<>();//答案需要的链表
        int n = nums.length;//n代表数组长度
        for (int i = 0; i < n - 2; ++i) {//因为需要3个数,所以第一个数最多到---倒数第3个
            int x = nums[i];//x保存当前遍历的第一个数
            if (i > 0 && x == nums[i - 1]) continue; // 跳过重复数字,枚举过的,就不重复枚举了
            // 优化一:因为数组排序后是从小到大,如果当前第一个数+它后面两个数,就已经>0了,那当前枚举,包括后面的,都不会符合条件
            if (x + nums[i + 1] + nums[i + 2] > 0) break; 
            // 优化二:如果当前数+倒数那两个数(从小到大排序,也就是末尾的都是最大的)都小于0的话,那也就不用在考虑这个枚举了。肯定枚举不出来
            if (x + nums[n - 2] + nums[n - 1] < 0) continue; 
            //左右指针
            int left = i + 1, right = n - 1;
            while (left < right) {//只要还有元素可以枚举就继续
                int s = x + nums[left] + nums[right];//3个数的和
                if (s > 0) --right;//如果s比0大,说明right指向的太大的,right--
                else if (s < 0) ++left;//如果s比0小,说明left指向太小,left++
                else {//如果s = 0,说明找到了,添加到链表,然后将继续进行下次枚举
                    ans.add(List.of(x, nums[left], nums[right]));//添加到链表
                    //进行下次枚举之前,我们可以跳过已经枚举过的,也就是和当前left和right数字重复的
                    //因为答案中不要重复的元素
                    for (++left; left < right && nums[left] == nums[left - 1]; ++left); // 跳过重复数字
                    for (--right; right > left && nums[right] == nums[right + 1]; --right); // 跳过重复数字
                }
            }
        }
        return ans;//返回答案
    }
}
  1. 方法二:使用hash表,用数组充当hash,空间复杂度不确定,取决于数组中存储的值的范围,如果一共有两个元素,[1,999999],那么空间复杂度就是999999. 所以,这是投机取巧的方法,但是做题的效率确实快。只用了0ms
    在这里插入图片描述
//C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        return nSum(nums, 3, 0);
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        return nSum(nums, 4, target);
    }

    public List<List<Integer>> nSum(int[] nums, int k, int target) {
        return new AbstractList<List<Integer>>() {
            final List<List<Integer>> res = new ArrayList<>();
            final List<Integer> path = new ArrayList<>();
            long min;

            @Override
            public List<Integer> get(int index) {
                init();
                return res.get(index);
            }

            @Override
            public int size() {
                init();
                return res.size();
            }

            public void init() {
                if (res.isEmpty()) {
                    int n = nums.length;
                    long[] Arr = new long[n];
                    Arrays.sort(nums);
                    min = nums[0];
                    for (int i = 0; i < n; i++) {
                        Arr[i] = nums[i] - min;
                    }
                    long NewTarget = (long)target - (long)k * min;
                    C(false, Arr, n, k, NewTarget);
                }
            }

            //C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
            public void C(boolean T, long[] a, int n, int k, long target) {
                if (n == 0 || k == 0) {
                    if (target == 0 && k == 0) {
                        res.add(new ArrayList<>(path));
                    }
                    return;
                }
                if (k == 2) {
                    if (!T && n != a.length && a[n] == a[n - 1]) {
                        return;
                    }
                    //两数之和模板
                    twoSum(a, 0, n - 1, target);
                    return;
                }
                if (n == k) {
                    if (!T && n != a.length && a[n] == a[n - 1]) {
                        return;
                    }
                    //数组中元素和是否等于target
                    sumArr(a, n, target);
                    return;
                }
                if (check(a, n, k, target)) {
                    return;
                }
                C(false, a, n - 1, k, target);
                if (!T && n != a.length && a[n] == a[n - 1]) {
                    return;
                }
                if (target - a[n - 1] >= 0) {
                    path.add((int) (a[n - 1] + min));
                    C(true, a, n - 1, k - 1, target - a[n - 1]);
                    path.remove(path.size() - 1);
                }
            }

            void twoSum(long[] a, int l, int r, long target) {
                if (l >= r || a[r - 1] + a[r] < target || a[l] + a[l + 1] > target) {
                    return;
                }
                while (r > l) {
                    long sum = a[l] + a[r];
                    if (sum < target) {
                        l++;
                    } else if (sum > target) {
                        r--;
                    } else {
                        path.add((int) (a[l] + min));
                        path.add((int) (a[r] + min));
                        res.add(new ArrayList<>(path));
                        path.remove(path.size() - 1);
                        path.remove(path.size() - 1);
                        while (r > l && a[l] == a[l + 1]) {
                            l++;
                        }
                        while (r > l && a[r] == a[r - 1]) {
                            r--;
                        }
                        l++;
                        r--;
                    }
                }
            }

            void sumArr(long[] a, int n, long target) {
                for (int i = n - 1; i > -1; i--) {
                    target -= a[i];
                    path.add((int) (a[i] + min));
                }
                if (target == 0) {
                    res.add(new ArrayList<>(path));
                }
                for (int i = n - 1; i > -1; i--) {
                    target += a[i];
                    path.remove(path.size() - 1);
                }
            }

            boolean check(long[] a, int n, int k, long target) {
                if (n - k < 0) {
                    return true;
                }
                long max = 0;
                long min = 0;
                for (int i = 0; i < k; i++) {
                    min += a[i];
                    max += a[n - i - 1];
                }
                if (target < min || target > max) {
                    return true;
                }
                return false;
            }
        };
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/367962.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于协同过滤的个性化电影推荐系统分析设计python+flask

本系统为用户而设计制作个性化电影推荐管理&#xff0c;旨在实现个性化电影推荐智能化、现代化管理。本个性化电影推荐自动化系统的开发和研制的最终目的是将个性化电影推荐的运作模式从手工记录数据转变为网络信息查询管理&#xff0c;从而为现代管理人员的使用提供更多的便利…

2401Idea用GradleKotlin编译Java控制台中文出乱码解决

解决方法 解决方法1 在项目 build.gradle.kts 文件中加入 tasks.withType<JavaCompile> {options.encoding "UTF-8" } tasks.withType<JavaExec> {systemProperty("file.encoding", "utf-8") }经测试, 只加 tasks.withType<…

谷粒商城【成神路】-【4】——分类维护

目录 1.删除功能的实现 2.新增功能的实现 3.修改功能的实现 4.拖拽功能 1.删除功能的实现 1.1逻辑删除 逻辑删除&#xff1a;不删除数据库中真实的数据&#xff0c;用指定字段&#xff0c;显示的表示是否删除 1.在application.yml中加入配置 mybatis-plus:global-config:…

俩种方法解决 VScode中 NPM 脚本消失,NPM 脚本未显示在资源管理器侧栏中

npm脚本是npm包管理器的一个功能&#xff0c;允许开发者在package.json文件中定义一系列命令脚本&#xff0c;用于执行各种开发任务。 今天打开准备运行的时候发现找不到NPM脚本了&#xff0c;左侧的一栏完全没有显示&#xff0c;在网上查阅了很多资料后总结出俩个方法可以用来…

寒假作业2月3号

第二章 引用内联重载 一&#xff0e;选择题 1、适宜采用inline定义函数情况是&#xff08;C&#xff09; A. 函数体含有循环语句 B. 函数体含有递归语句 C. 函数代码少、频繁调用 D. 函数代码多、不常调用 2、假定一个函数为A(int i4, int j0) {;}, 则执行“A (1);”语句…

解密二进制世界:Hex-Rays IDA Pro forMac/win交互式反汇编工具

在当今数字化时代&#xff0c;软件和硬件的安全性成为了重中之重。为了保护软件和硬件免受黑客和恶意攻击的威胁&#xff0c;人们需要了解和分析代码的内部结构和工作原理。而Hex-Rays IDA Pro作为一款强大的交互式反汇编工具&#xff0c;为安全专业人士提供了解密二进制世界的…

Juc07_乐观锁和悲观锁、公平锁和非公平锁、递归锁(可重入锁)、死锁及排查、自旋锁

1、 乐观锁和悲观锁 ①. 悲观锁(synchronized关键字和Lock的实现类都是悲观锁) 什么是悲观锁&#xff1f;认为自己在使用数据的时候一定有别的线程来修改数据&#xff0c;因此在获取数据的时候会先加锁&#xff0c;确保数据不会被别的线程修改适合写操作多的场景&#xff0c;…

lua 语法介绍与 NGINX lua 高级用法实战操作

文章目录 一、概述二、lua 安装三、lua 语法1&#xff09;lua 数据类型2&#xff09;lua 变量3&#xff09;lua 拼接字符串4&#xff09;lua 循环5&#xff09;lua 函数6&#xff09;lua 条件控制7&#xff09;lua 库模块 四、NGINX lua 高级用法 一、概述 lua是一种轻量小巧的…

【AI绘画UI+Windows部署】Fooocus:Controlnet原作者结合了sd的开源和Midjourney重新设计的UI

代码&#xff1a;https://github.com/lllyasviel/Fooocus windows一键启动包下载&#xff1a;https://github.com/lllyasviel/Fooocus/releases/download/release/Fooocus_win64_2-1-831.7z B站视频教程&#xff1a;AI绘画入门神器&#xff1a;Fooocus | 简化SD流程&#xff0c…

Boosting semantic human matting with coarse annotations

前向推理在modelscope中开源了&#xff0c;但是训练没开源&#xff0c;且是基于TensorFlow的&#xff0c;复现起来是比较麻烦的。 1.Introduction 分割技术主要集中在像素级二元分类&#xff0c;抠图被建模为前景图像F和背景图像B的加权融合&#xff0c;大多数matte方法采用指…

不做中位剧的腾讯,能靠精品撑起长视频会员吗?

回顾腾讯视频的2023年,马化腾用“厚积薄发”来形容。 在腾讯年会上,马化腾回顾了过去一年长视频业务板块的发展情况,同时也清晰地提出了未来的规划,总结来说就是以下三点: 1、《繁花》《三体》《漫长的季节》是腾讯过去一年特别出彩的剧集,几部大剧撑起了长视频会员业务…

设计模式——2_1 命令(Command)

文章目录 定义图纸一个例子&#xff1a;空调和他的遥控器只有控制面板的空调遥控器可以撤销的操作 碎碎念命令和Runnable命令和事务 定义 把请求封装成一个对象&#xff0c;从而使你可以用不同的请求对客户进行参数化&#xff0c;对请求排队或记录请求日志&#xff0c;以及支持…

Spring Bean 生命周期常见错误

虽然说 Spring 容器上手简单&#xff0c;可以仅仅通过学习一些有限的注解&#xff0c;即可达到快速使用的目的。但在工程实践中&#xff0c;我们依然会从中发现一些常见的错误。尤其当你对 Spring 的生命周期还没有深入了解时&#xff0c;类初始化及销毁过程中潜在的约定就不会…

超越现实,体验无限可能——VMware Workstation 的魅力之旅

随着科技的飞速发展&#xff0c;虚拟化技术已经深入人心&#xff0c;成为现代人工作与学习的必备工具。在这其中&#xff0c;VMware Workstation以其卓越的性能和稳定的运行环境&#xff0c;成为众多电脑爱好者和专业人士的首选。今天&#xff0c;让我们一起探索VMware Worksta…

初探unity中的ECS

ECS是一种软件架构模式&#xff0c;就像MVC一样。ECS最早在游戏《守望先锋》中提及到的相关链接。ECS具体是指实体&#xff08;entity&#xff09;、 组件&#xff08;component&#xff09;和系统&#xff08;system&#xff09;&#xff1a; 实体&#xff1a;实体是一个ID&a…

docker踩坑记录

踩坑记录 1.1 后台启动容器&#xff0c;实际没有启动 现象&#xff1a; 后台启动centos&#xff0c;结果执行docker ps命令&#xff0c;容器没启动。 原因&#xff1a; docker是以容器启动的&#xff0c;必须要有个前台进程&#xff0c;若是全部都是后台deamon守护进程&…

C语言第十七弹---指针(一)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 指针 1、内存和地址 1.1、内存 2、指针变量和地址 2.1、取地址操作符&#xff08;&&#xff09; 2.2、指针变量和解引用操作符&#xff08;*&#xff09;…

数字巨轮航行大数据海洋:数据可视化引领时代潮流

在大数据时代的潮流中&#xff0c;数据可视化如同一艘畅行无阻的科技巨轮&#xff0c;引领我们穿越数字浩瀚的大海&#xff0c;使我们在信息的航程中游刃有余。下面我就从可视化从业者的角度&#xff0c;来简单说说数据可视化是如何帮助我们在大数据时代畅行无阻的。 数据可视化…

Python 数据分析(PYDA)第三版(七)

原文&#xff1a;wesmckinney.com/book/ 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 附录 附录 A&#xff1a;高级 NumPy 原文&#xff1a;wesmckinney.com/book/advanced-numpy 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 此开放访问网络版本的《Pyt…

苹果电脑Mac清理内存怎么清理卸载残留

苹果电脑中的应用程序大部分是可以通过将其拖拽至废纸篓并倾倒来卸载的。但是部分程序在卸载后仍有残留文件&#xff0c;比如support文件和pref设置等文件的。小编今天介绍下苹果电脑清理内存怎么清理卸载残留以及好用的清理技巧分享。 一、苹果电脑清理内存怎么清理卸载残留 …