LeetCode关于数组中求和的题型
2024-09-15 01:39:03
15. 3Sum:三数之和为0的组合
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
思路:循环法,先给数组排序->[-4,-1,-1,0,1,2],其中i,j,k三数的下标,i先为最左边的一个数,则i<n-3,此时可以根据求两数之和的方法来进行求解;
对一个有序的数组求两数之和为定值,最简单的方法为j,k分别为数组的两端,主键向中间靠拢;
具体代码如下:
import java.util.*;
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
if(nums==null||nums.length==0)
return lists;
Arrays.sort(nums);
int n = nums.length;
int i=0;
while(i<=n-3){
int j=i+1;
int k = n-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]==0){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
lists.add(list);
while(j<k&&nums[j]==nums[j+1])
j++;
while(k>j&&nums[k]==nums[k-1])
k--;
j++;
k--;
}else if(nums[i]+nums[j]+nums[k]<0){
j++;
}else{
k--;
}
}
while(i<n-1&&nums[i]==nums[i+1])
i++;
i++;
}
return lists;
}
}
最新文章
- 新语言代码高亮及Windows Live Writer插件开发
- Python将文本生成二维码
- adnroid仿miui的dialog
- 封装使用ViewHolder模式的Adapter组件,及用其快速实现聊天界面
- 记一个万金油开源框架JHipster
- unity零基础开始学习做游戏(六)背景给我“滚”~
- TOMCAT --->; servlet概念
- Linux系统下安装Angular2开发环境(Ubuntu16.0和deepin)
- 基于ModBus-TCP/IT 台达PLC 通讯协议解析
- 纯 Html 5的 简单 TreeView 保存下思路以后有机会再完善。
- 00-python-常用命令
- Maven的配置与下载
- CM记录-集群运行故障修复记录
- 新书《深入应用C++11:代码优化与工程级应用》出版,感谢支持
- Navicat新建查询,系统找不到指定路径 独家解决办法
- 老齐python-基础6(循环 if while for)
- fastcgi_finish_request
- php7安装及和php5的共存
- Lazarus教程 中文版后续给出
- UIAlertController 实现kvo实现mes文字设置
热门文章
- POJ1015陪审团(Jury Compromise)——dp+路径记录
- js正则表达式30分钟入门教程
- dede的织梦问答模块也可以支持arclist标签
- 如何在eclipse中安装angularjs插件
- Zeroc Ice 3.6.1 生成 vs2015 c++ 版本库及相关配置
- Jmeter接口压测
- [UE4]事件处理(Handling Events)和委托(Delegate)代码示例(一)
- SQL Server 2008 CDC增量变更捕获详解
- Parallel I/O and Columnar Storage
- 微信小程序教程系列