当前位置:网站首页>Sum of three numbers: (sort + double pointer + pruning)
Sum of three numbers: (sort + double pointer + pruning)
2022-07-23 10:15:00 【Jingle!】
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
//1. Sort the array first : Sorting algorithm can be used here : Quick sort 、 Merge sort .
Arrays.sort(nums);
//2. Double pointer , One from the front , One from the back
for (int i = 0; i < nums.length; i++) {
// After sorting, if the first element is greater than zero , So no combination can make up a triple , Just return the result directly
if (nums[i] > 0) {
return res;
}
// Pruning operation : The first element is de duplicated ;(i > 0 To prevent index exceptions )
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip all duplicate values
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// Find out , Correction and contraction at the same time
right--;
left++;
} else if (sum > 0) {
right--;
} else {
left++;
}
}
}
return res;
}边栏推荐
- 【Azure 事件中心】Azure Event Hub 新功能尝试 -- 异地灾难恢复 (Geo-Disaster Recovery)
- What are you doing at two in the morning?
- Ten year structure five year Life-05 first business trip
- 博世BOSCH EDI项目案例
- error MSB4181: “QtRunWork”任务返回了 false,但未记录错误
- 【机器学习基础】特征工程常用操作
- The gospel of small and medium-sized enterprises is coming! Jnpf is becoming popular, helping business digital upgrading
- Ten years of sharpening a sword, the core technology evolution of the cloud native distributed database polardb-x
- 转行软件测试薪资10K | 手中有粮心中有底,在任何时候都是真理
- Android development learning diary - content provider (cross application database modification)
猜你喜欢

C language flexible array

Ten years of sharpening a sword, the core technology evolution of the cloud native distributed database polardb-x

Seven sorts -- detailed explanation of ten thousand words

数据中台、BI业务访谈(三):如何选择合适的访谈对象

多线程中的「lost wake up 问题」| 为什么wait()和notify()需要搭配synchonized关键字使用?

Decompile the jar package / class file / modify the jar package using the decompile plug-in of idea

可视化全链路日志追踪

博世BOSCH EDI项目案例

如何在OneFlow中新增算子

Airtest脚本的点击位置与点击偏移
随机推荐
Leetcode 1074. number of submatrices that sum to target
Android development learning diary - content provider (cross application database modification)
Nine charts overview the cycle law of encryption Market
范式及反范式
A brief tutorial for soft exam system architecture designer | requirements engineering
华泰证券自己能开户吗安全吗?多久能开完
1.赋值语句
软考 系统架构设计师 简明教程 | 需求工程
Tsinghua, air, Tencent | 3D isovariant molecular map pre training
ARP Spoofing protection of network security
多线程中的「lost wake up 问题」| 为什么wait()和notify()需要搭配synchonized关键字使用?
转行软件测试薪资10K | 手中有粮心中有底,在任何时候都是真理
Open source Invoicing system, 10 minutes to complete, it is recommended to collect!
Scala对象object
如何将list中相同字段值归类在同一个list下
在线问题反馈模块实战(十一):实现图片下载功能
【C语言基础】16 可变数组(数组长度可扩展)
Anaconda 换源以及安装opencv
如何在OneFlow中新增算子
【MySQL】游标「Cursor」