三数之和问题
2023-02-18 16:36:38 时间
三数之和问题
作者:Grey
原文地址:
题目描述
思路
求三个数的和为0的子数组有哪些,我们可以转换一下,考虑一下求两个数之和等于某个target
的子数组有哪些,
假设我们已经实现了这个方法:
List<List<Integer>> twoSum(int[] numbers, int start, int end, int target)
这个方法表示:在numbers
这个有序数组中,从start
到end
这个数组下标区间内,两个数之和为target
的所有子数组有哪些
假设上面这个方法实现了,那么我们可以通过这个方法来求我们这个三数之和为0的问题,
我们可以:
for(int i = len - 1; i >= 2; i++) {
...
List<List<Integer>> list = twoSum(numbers,0, i-1, -numbers[i] )
...
}
这样来求三数和为0的问题。
那么在有序数组中,怎么求两数之和为target
比较快呢?
我们可以设置两个指针。一个指向start
, 一个指向end
, 先看start
对应的值加上end
对应的值之和(我们假设为sum
)与target
之间的关系,
如果: sum > target
那么: end--
如果: sum < target
那么: start++
如果:sum == target
那么:收集答案
这里还有一些细节需要注意,就是数组中可能有重复元素,而题目要求不能有重复的元组,
那么在每次start++
,或者end--
的时候,都要判断移动到新的数是否和原数一样,如果一样,直接继续start++
,或者end--
直到下一个和原数不相等的数才停止。
完整代码如下:
public List<List<Integer>> threeSum(int[] numbers) {
if (null == numbers || numbers.length == 0) {
return new ArrayList<>();
}
int size = numbers.length;
List<List<Integer>> result = new ArrayList<>();
// 先排序 O(N*logN)
Arrays.sort(numbers);
for (int i = size - 1; i >= 2; i--) {
if (i == size - 1 || numbers[i] != numbers[i + 1]) {
// 必须要移动到下一个不等于number[i]的数才不会出现重复
List<List<Integer>> lists = twoSum(numbers, 0, i - 1, -numbers[i]);
if (null != lists && 0 != lists.size()) {
for (List<Integer> list : lists) {
list.add(numbers[i]);
result.add(list);
}
}
}
}
return result;
}
// start ... end 之间是有序的
public List<List<Integer>> twoSum(int[] numbers, int start, int end, int target) {
List<List<Integer>> list = new ArrayList<>();
while (start < end) {
int startVal = numbers[start];
int endVal = numbers[end];
int sum = startVal + endVal;
if (sum < target) {
while (start < end && numbers[start] == startVal) {
// 必须要移动到下一个不为startVal的数才不会出现重复
start++;
}
} else if (sum > target) {
while (end > start && numbers[end] == endVal) {
end--;
}
} else {
// sum == target
List<Integer> pair = new LinkedList<>();
pair.add(startVal);
pair.add(endVal);
list.add(pair);
while (start < end && numbers[start] == startVal) {
start++;
}
}
}
return list;
}
更多
相关文章
- [javascript]使用正则替换url中最后面的斜杠
- [Go] Golang中的面向对象
- [Go] 分页计算页码的主要逻辑
- [Go] gocron源码阅读-go语言中数组和切片的字面值初始化语法
- [PHP]面向对象多态性的体现
- [Linux] 纯净ubuntu快速搭建宝塔面板
- [操作系统]内存页面置换算法
- 主干开发前要知道的,4错误认识+3优势
- 【高热FAQ】关于智慧康养物联网加速器 ,你想知道的都在这
- 保姆级带你深入阅读NAS-BERT
- 想要面试大数据工作的50道必看题
- 如何支撑企业快速构建数字孪生体
- 带你掌握不同平台下,探索JDK源码所需的native方法
- 敏捷开发你必须知道的7件事
- 带你上手全新版本的Webpack 5
- 你真的会使用数据库的索引吗?
- 云小课丨SA基线检查:给云服务来一次全面“体检”
- 画一个清晰明了的时序图,要掌握这三点
- 华为云企业级Redis:助力VMALL打造先进特征平台
- 解读鸿蒙轻内核的监控器:异常钩子函数