牛客网编程高频题31——NC54数组中相加和为0的三元组
2021/6/10 20:23:03
本文主要是介绍牛客网编程高频题31——NC54数组中相加和为0的三元组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
数组中相加和为0的三元组
描述
示例1
示例2
示例3
方法:循环搜索
数组中相加和为0的三元组
描述
给出一个有n个元素的数组S,S中是否有元素a、b、c满足a+b+c=0?找出数组S中所有满足条件的三元组。
注意:
- 三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)
- 解集中不能包含重复的三元组。
例如,给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)
示例1
输入
[0]返回值
[]
示例2
输入
[-2,0,1,1,2]返回值
[[-2,0,2],[-2,1,1]]
示例3
输入
[-10,0,10,20,-10,-40]返回值
[[-10,-10,20],[-10,0,10]]
方法:循环搜索
先将数组排序,然后从小到大开始遍历,这里我用的是三个循环,也可以一个循环加双指针,
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { ArrayList<Integer> arr=new ArrayList<>(); ArrayList<ArrayList<Integer>> res=new ArrayList<>(); if (num.length<3) return res; Arrays.sort(num);//将数组从小到大进行排序 if (num[num.length-1]<0) return res;//若数组最大的元素都小于0或者元素个数不超过3个,则没有满足的三元组 for (int i = 0; i < num.length-2; i++) { if (num[i]>0) break; if(i>0 && num[i]==num[i-1]) continue; for (int j = i+1; j < num.length-1; j++) { if(j>i+1 && num[j]==num[j-1]) continue; int need=0-num[i]-num[j]; if (need>num[num.length-1] || need<0) continue; for (int k = j+1; k < num.length; k++) { if (need<num[k]){ break; }else if (need==num[k]){ ArrayList<Integer> triple=new ArrayList<>(); triple.add(num[i]);triple.add(num[j]);triple.add(num[k]); res.add(triple); break; } } } } return res; } }
该方法时间和空间消耗表现较好,
这篇关于牛客网编程高频题31——NC54数组中相加和为0的三元组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享