LeetCode15.三数之和

embedded/2024/12/22 15:12:55/

题目链接:15. 三数之和 - 力扣(LeetCode)

1.常规解法(会超时)

由于这道题需要排除相同的三元组,则可以先将目标数组从小到大排序,再遍历数组找到每个符合条件的三元组,若结果中不包含该三元组,就将该结果添加到目标结果中,代码如下:

javascript">    public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 2; i++) {for (int j = i + 1; j < n - 1; j++) {for (int k = j + 1; k < n; k++) {if (nums[i] + nums[j] + nums[k] == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);if (!ret.contains(list)) {ret.add(list);}}}}}return ret;}

2. 双指针算法

和常规解法一样,我们要先将目标数组从小到大排序,由于要求三数之和等于0,我们可以先固定一个数,只需找到剩下的哪两个数与这个数的和为0,再定义一个顺序表存放三元组。

定义三个指针left,right,p,先将p固定在最后一个数,left在第一个数的位置,right在倒数第二个数的位置,接下来在每一轮循环中,保持p不动,只要移动left和right即可。

当nums[left] + nums[right] + nums[p] > 0,由单调性知,若保持right不动,left右边的数均大于left指向的数,导致三数之和只会越加越大(数组是从大到小排序的),这时就要将right向左移动一位;当nums[left] + nums[right] + nums[p] < 0,由单调性知,若保持left不动,right左边的数均小于right指向的数,导致三个数之和会越加越小,这是就要将left向右移动一位;当nums[left] + nums[right] + nums[p] == 0,就要将这个结果添加到顺序表中,由于最后的结果不允许出现相同的三元组,这时就要去重。

去重:若使用contains判断三元组是否重复,代码就会超时,这时我们就要在nums[left] + nums[right] + nums[p] == 0时,将与left和right指向的数的相同的数去掉,由于这个数组是有序的,那么相同的数就会聚集在一起,只需要使用while循环去重即可;相同的,当left与right相遇时,第一轮循环结束,也去要进行去重操作,将与p指向的数相同的数跳过即可。

优化:当p指向的元素小于0时,由单调性知,p左边的元素均小于0,就不存在三个数之和为0的情况,直接返回结果即可。

流程图与代码如下:

java">    public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length;int p = n - 1;while (p > 1) {int left = 0;int right = p - 1;if (nums[p] < 0) {return ret;}while (left < right) {if (nums[left] + nums[right] + nums[p] < 0) {left++;} else if (nums[left] + nums[right] + nums[p] > 0) {right--;} else {List<Integer> list = new ArrayList<>();list.add(nums[left]);list.add(nums[right]);list.add(nums[p]);ret.add(list);int numLeft = nums[left++];while (nums[left] == numLeft && left < right) {left++;}int numRight = nums[right--];while (nums[right] == numRight && left < right) {right--;}}}int numP = nums[p--];while (nums[p] == numP && p > 1) {p--;}}return ret;}

 希望大家积极指出不足之处


http://www.ppmy.cn/embedded/127878.html

相关文章

从“寻鲜市集”看巴奴产品主义的「新生命力」

【潮汐商业评论/原创】 “这个就是获得‘国家地理标志产品’的金阳青花椒&#xff0c;七分麻三分香&#xff0c;是麻辣火锅的灵魂&#xff1b;这个菌汤用了3种云南野生牛肝菌熬制&#xff0c;味道鲜香&#xff0c;口感顺滑&#xff1b;还有这个龙竹鲜笋可不得了&#xff0c;它…

Qt/C++编写的mqtt调试助手使用说明

一、使用说明 第一步&#xff0c;选择协议前缀&#xff0c;可选mqtt://、mqtts://、ws://、wss://四种&#xff0c;带s结尾的是走ssl通信&#xff0c;ws表示走websocket通信。一般选默认的mqtt://就好。第二步&#xff0c;填写服务所在主机地址&#xff0c;可以是IP地址也可以…

16.C++程序中的文件操作

C 中的文件操作是指程序与外部文件进行交互的过程&#xff0c;包括文件的打开、读取、写入和关闭等操作。 1. 文件流对象 C 中主要使用标准库中的文件流对象来进行文件操作&#xff1a; 输入文件流&#xff1a;std::ifstream输出文件流&#xff1a;std::ofstream 2. 文件操…

2-119 基于matlab的合成孔径雷达(SAR)RDA(距离多普勒算法)、RMA(距离徙动算法)、CSA(线性调频变标算法)算法点目标成像与分析

基于matlab的合成孔径雷达(SAR)RDA(距离多普勒算法)、RMA(距离徙动算法)、CSA(线性调频变标算法)算法点目标成像与分析&#xff0c;RDA算法通过参考目标的多普勒历程完成对应匹配滤波器设计&#xff0c;获得同距离处不同目标相对于参考目标的方位位置。RMA是一种高分辨率的频域…

MySQL 的数据类型

1.整数类型 1.1 tinyint tinyint 为小整数类型&#xff0c;存储空间为1个字节&#xff08;8位&#xff09;&#xff0c;有符号范围-128 ~ 127&#xff0c;无符号范围 0 ~ 255,此类型通常在数据库中表示类型的字段&#xff0c;如某一字段 type 表示学科,其中 “type1” 表示语文…

搭建一个vue3+vite框架

可以使用以下两种搭建方式 通过create-vue搭建vue3 项目&#xff08;建议使用&#xff09; create-vue create-vue 是 Vue.js 官方推荐的用于快速启动 Vite 驱动的 Vue 项目的脚手架工具。它简化了创建新 Vue 项目的过程&#xff0c;提供了预配置的项目结构&#xff0c;并集…

Redis 5 种基本数据类型的前两个详解

Redis 共有 5 种基本数据类型&#xff1a;String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Set&#xff08;集合&#xff09;、Hash&#xff08;散列&#xff09;、Zset&#xff08;有序集合&#xff09;。 这 5 种数据类型是直接提供给用户使用的&…

高性能亿级录制列表查询系统设计实践

作者:jaskeylin,腾讯会议后台架构师。Apache RocketMQ committer、拥有11年中间件产品和和大型业务后台的双背景研发经历,对海量用户、高并发、多地域容灾等架构设计拥有丰富经验,热衷与技术总结和知识分享。 一 背景 在腾讯会议320的APP改版中,我们需要构建一个一级TAB,…