LeetCode做题总结 15. 三数之和、18. 四数之和 (Java)

不会做,参考了代码随想录和力扣官方题解,对此题进行整理。

X数之和

  • 15. 三数之和
    • 代码思路
    • 20240103重写
      • 错误1
      • 错误2
      • Java语言点总结
  • 18. 四数之和
    • 代码思路
    • 20240104
      • (伪)错误1 第一次剪枝
      • 错误2 第二次剪枝
      • 错误3 溢出

15. 三数之和

代码思路

思想:利用双指针法,对数组从小到大排序。先固定一个数,找到其他两个。

(1)首先对数组从小到大排序。
在这里插入图片描述
(2)a从左到右遍历数组,每一次遍历的时候设置left指针,right指针。num[a]+num[left]+num[right],如果值等于0,相当于找到了目标元组。如果值大于0,right–;如果值小于0,left++。

(3)涉及到去重的问题。a、left、right都会重复,具体请看下图(↑指a; -指left; =指right)。
在这里插入图片描述a去重:如果在这次循环之前,已经判断了三元组之一的元素num[a](不管是符合条件还是不符合条件,已经判断过这个元素),都跳过。if (num[a] >num[a-1]) continue;
为什么这里不用num[a]和num[a+1]比较,因为会出现元组 -1 -1 2。这是符合条件的。num[a] 和num[a-1]保证的是,在本次循环之前已经判断过这个元素;num[a]和num[a+1]比较还continue的话就是不允许三元组里有重复的元素。

left去重、right去重:找到一个目标元组之后,(且上一步a去重),现在要对left、right去重。如果num[left+1] =num[left], left++;如果num[right-1] =num[right], right–。

(4)技巧:三个数num[a]、num[left]、num[right]相加等于零,因为初始值 left=a+1,right=num.length-1,所以a<left<right这个等式恒成立。又因为num数组从小到大排序,三个数中最小的是a,如果a>0,那么一定不存在这个元组。

20240103重写

20240103第一次重写,错了很多,对着答案改。
语言是 java。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 不知道怎么初始化List<List<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);//写错了Arrays.sort(),我写少了一个s

        int left,right;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                return ans;
            }

            if(i>0 && nums[i]==nums[i-1]) { //是i>0,不是i>1
                continue;
            }

            left = i+1;
            right = nums.length-1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0) {
                    right--;
                } else if(sum < 0) {
                    left++;
                } else {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));//不会写
                    while(right > left && nums[left+1] == nums[left]) {left++;}//为什么要设置right > left
                    while(right > left && nums[right-1] == nums[right]) {right--;}

                    //漏写了。
                    right--; 
                    left++;
                }
            }
        }

        return ans;
    }
}

错误1

错误:我在代码中写了 List<List<Integer>> a=new ArrayList<ArrayList<Integer>>();
报错信息:ArrayList<ArrayList<Integer>> cannot be converted to List<List<Integer>>

List<List<Integer>>是在List1<>中再放一个List2<>,List1中每个List2的长度可以是任意的,而不是像二维数组那样维度固定。
List<List<Integer>> 的初始化为 List<List<Integer>> a=new ArrayList<List<Integer>>();

这个与泛型有关,但我还没学到那里,CSDN 有一篇文章讲的不错:跳转链接
在这里插入图片描述

错误2

有可能会出现 -2 1 1 1 1 1 1 1 的情况,所以 left++ right- -的时候一定要保证 left<right
在这里插入图片描述
在这里插入图片描述

Java语言点总结

  1. Arrays.sort()
  2. List<List<Integer>> 的初始化为 List<List<Integer>> a=new ArrayList<List<Integer>>();
  3. Arrays.asList() 该方法是将数组转化成List集合的方法
  4. List中 用add方法添加成员

18. 四数之和

代码思路

和三数之和一样。
五数、六数之和都是一样的。

20240104

又看了代码随想录的分析才写出来的。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(nums); 

        for(int k = 0; k < nums.length; k++) { // nums.size 是否有必要?
            if(k > 0 && nums[k] == nums[k-1]) {
                continue;
            }

            if(nums[k]>0 && nums[k]>target) {//错了 if(target>0 && nums[k]>target)
                return ans;
            }//如果target小于零,nums[k]>target 不能跳过 [-4,-1,0,0] TARGET=-5
           
            for(int i = k+1; i < nums.length; i++) {
                if(i > k+1 && nums[i] == nums[i-1]) {
                    continue; // i=k+1,nums[k+1]=nums[k]不能跳过
                }

                if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0) {
                    break;//这里是break不是return
                }

                int left = i+1;
                int right = nums.length-1;
                while(left < right) {
                    long sum =(long) nums[left] + nums[right] + nums[k] +nums[i];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        ans.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
                        while(left < right && nums[left+1] == nums[left]) left++;
                        while(left < right && nums[right-1] == nums[right]) right--;

                        left++;
                        right--;
                    }
                }
            }
        }

        return ans;
    }
}

在这里插入图片描述

(伪)错误1 第一次剪枝

最开始写成: if(target>0 && nums[k]>target)
代码随想录写法:if(nums[k]>0 && nums[k]>target)
刚刚又试了一下,其实都是对的。之前报错是因为第二次剪枝的break和return出错。

错误2 第二次剪枝

最开始写成:

if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0) {
  return;
}

正确写法:

if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0) {
  break;
}

对比了代码随想录C++的代码(代码随想录Java的代码没有第二次剪枝),我一直以为是大于等于出错,或者是 &&的左右顺序出错,其实是 break和 return的区别。

错误3 溢出

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

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

相关文章

C#使用纯OpenCvSharp部署yolov8-pose姿态识别

【源码地址】 github地址&#xff1a;https://github.com/ultralytics/ultralytics 【算法介绍】 Yolov8-Pose算法是一种基于深度神经网络的目标检测算法&#xff0c;用于对人体姿势进行准确检测。该算法在Yolov8的基础上引入了姿势估计模块&#xff0c;通过联合检测和姿势…

vue icon 本地正常 线上打包失败变乱码

出现这个原因是因为sass解析的问题 Node版本高的话可以通过升级sass版本 并且配置vue.config规避这个问题 //给sass配置的东西 这个对应的版本是sass 1.39.0 本人node版本v14 升级sass版本后出现报错css: {loaderOptions: {scss: {additionalData: import "/styles/var…

网络请求 - 异步编程详解

一、概述 网络管理模块主要提供以下功能&#xff1a; HTTP数据请求&#xff1a;通过HTTP发起一个数据请求。WebSocket连接&#xff1a;使用WebSocket建立服务器与客户端的双向连接。Socket连接&#xff1a;通过Socket进行数据传输。 HTTP和WebSocket都是啥&#xff1f; 比如我…

速记计算机网络传输介质分类

计算机网络中的传输介质是指用于在不同设备之间传递数据的物理媒介。传输介质的选择对于网络的性能和可靠性至关重要。在计算机网络中&#xff0c;常见的传输介质可以分为有线传输介质和无线传输介质两类。本文将对这两类传输介质进行详细的分类和介绍。 一、有线传输介质 有…

外包干了4个月,技术退步明显了...

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01; 而我已经在一个企业干了四…

[C]jupyter中使用C

[C]jupyter中使用C 安装使用用处 安装 https://github.com/brendan-rius/jupyter-c-kernel 下拉找到3条命令&#xff0c;装就可以了 mac和linux可用 python3可用&#xff0c; 2不可以 第二条命令可以改为 : python3 install_c_kernel 小总结&#xff1a;如果有问题&#xff0…

Merge还是Rebase?这次终于懂了

《Git分支管理&#xff1a;Merge还是Rebase&#xff1f;》 导语&#xff1a; 在Git的分支管理中&#xff0c;Merge和Rebase是两种常见的合并策略&#xff0c;每一种都有其优劣之处。究竟应该选择Merge还是Rebase&#xff0c;取决于项目的需求和团队的工作流程。本文将深入探讨…

echarts 仪表盘进度条 相关配置

option {series: [{type: gauge,min: 0,//最大值max: 100, //最小值startAngle: 200,//仪表盘起始角度。圆心 正右手侧为0度&#xff0c;正上方为90度&#xff0c;正左手侧为180度。endAngle: -20,//仪表盘结束角度splitNumber: 100, //仪表盘刻度的分割段数itemStyle: {color…

WPF 使用矢量字体图标

矢量字体图标 在WPF项目中经常需要显示图标&#xff0c;但是项目改动后&#xff0c;有时候需要替换和修改图标&#xff0c;这样非常麻烦且消耗开发和美工的时间。为了快速开发项目&#xff0c;节省项目时间&#xff0c;使用图标矢量字体图标是一个非常不错的选择。 矢量字体图标…

【java爬虫】首页显示沪深300指数走势图以及前后端整合部署方法

添加首页 本文我们将在首页添加沪深300指数成立以来的整体走势数据展示&#xff0c;最后的效果是这样的 单独贴一张沪深300整体走势图 我感觉从总体上来看指数还是比较稳的&#xff0c;没有特别大的波动&#xff0c;当然&#xff0c;这只是相对而言哈哈。 首先是前端页面 &l…

C++性能优化- perf 和火焰图的安装使用

工欲善其事必先利其器&#xff0c;要想做Linux下的程序性能优化&#xff0c;就得先知道当前性能的瓶颈在哪里。 这里主要介绍一下常用的工具&#xff1a;perf工具和火焰图的使用方法 本文中的命令都是自己在Ubuntu18.04系统上测试可用的&#xff0c;在其他系统可能会需要不同的…

数据库的连接

连接数据库 我们使用WinR输入cmd打开运行窗口 输入:sqlplus并回车 输入用户名和密码,我用的是Scott,密码我自己设置的123456,Scott默认的密码是tiger,回车 这种情况表示登录成功 在连接Scott成功的情况下创建一些数据,在我的资源里面有个Oracle数据基础可以下载,直接复制粘…

HarmonyOS 开发基础(六)Slider

HarmonyOS 开发基础&#xff08;六&#xff09;Slider Entry Component struct Index {build() {Row() {Column() {// Slider&#xff1a;ArkUI 的基础组件 滑动条组件// options 参数&#xff1a;Slider 基础设置Slider({// 最小值min: 20,// 最大值max: 200,// 当前值value: …

使用Spring Retry优雅的实现业务异常重试

在系统中经常遇到业务重试的逻辑&#xff0c;比如三方接口调用&#xff0c;timeout重试三遍&#xff0c;异常处理重试的兜底逻辑等。那你是不是还在用下面这种方式呢&#xff1a; 我想大家可能很多时候也会这么写&#xff0c;这是能想到的第一个方法&#xff0c;但是我们这段代…

AP2813 双路降压恒流驱动IC 一路内置1A一路外置3A LED储能指示灯线路

产品描述 AP2813 是一款双路降压恒流驱动器,高效率、简单、内置功率管&#xff0c;适用于 5-80V 输入的高精度降 压 LED 恒流驱动芯片。内置功率管输出功率可达 12W&#xff0c;电流 1.2A。 AP2813 一路直亮&#xff0c;另外一路通过 MODE1 切换 全亮&#xff0c;爆闪。AP2813…

嵌入式(四)定时器 | 定时器功能 分类 定时器工作模式 寄存器全介绍

文章目录 1 定时器工作原理2 定时器功能3 定时器分类3.1 定时器13.2 定时器23.3 定时器3和定时器43.4 睡眠定时器3.5 看门狗定时器 4 定时器工作模式4.1 自由运行模式4.2 模模式4.3 正计数/倒计数模式 5 定时器1寄存器5.1 计数寄存器5.2 计数控制寄存器 6 定时器的两种使用方式…

junit单元测试:使用@ParameterizedTest 和 @CsvSource注解简化单元测试方法

在平常的开发工作中&#xff0c;我们经常需要写单元测试。比如&#xff0c;我们有一个校验接口&#xff0c;可能会返回多种错误信息。我们可以针对这个接口&#xff0c;写多个单元测试方法&#xff0c;然后将其场景覆盖全。那么&#xff0c;怎么才能写一个测试方法&#xff0c;…

实验笔记之——基于Linux服务器复现Instant-NGP及常用的tmux指令

之前博客实现了基于windows来复现Instant-NGP&#xff0c;本博文在linux服务器上测试 实验笔记之——基于windows复现Instant-NGP-CSDN博客文章浏览阅读444次&#xff0c;点赞15次&#xff0c;收藏7次。之前博客对NeRF-SLAM进行了调研&#xff0c;本博文先复现一下Intant-NGP。…

C++开发小技巧

C开发一些小技巧 积累一些能用得到的C开发小技巧。 错误码/状态码 错误码/状态码在项目很常见&#xff0c;用于提示错误类型、状态&#xff0c;通常还会附带一些相关描述。通常错误码是统一管理的&#xff0c;例如使用宏或者枚举定义。 平时我的做法 使用宏或者枚举定义错…

rust 注释文档生成 cargo doc

rust的cargo文档生成 只需要在每个函数写清楚注释&#xff0c;就可以自动生成文档&#xff0c;很方便 即不用写文档&#xff0c;又可以快速查看&#xff0c;是开发rust的必备技能 rust安装和开发环境配置&#xff0c;可以参考&#xff1a;链接 1.写注释的方法 连续三个 \ 即…