趣味算法题

越刷越上头的趣味算法题
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

三大利器解决三数之和问题

发布于 2024-03-13 | 更新于 2024-08-21

题目:15. 三数之和[1]

如果您已经有思路了,或者是N刷了,可以先自己写一遍。

题目分析

题目说明:给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 abc ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意,与两数之和不同,这里返回的是元素,不是下标。

解题思路

这个问题可以通过使用排序双指针技术来解决。为了避免重复的三元组,首先应该对数组进行排序,然后通过两头夹逼法,找出所有可能的两个数和当前元素相加结果为0。

最重要的:题目中并没有规定不能有重复元素,为了避免添加重复的三元组,我们需要跳过数组中重复的元素

具体步骤如下:

  1. 排序:首先,将数组排序。这是解决问题的前提,因为排序后可以使用双指针技术,并且更容易避免重复的三元组。
  2. 遍历:然后,遍历排序后的数组,对于每个元素,使用双指针找出所有可能的两个加数,使它们的和加上当前元素的值为0。
  3. 两头夹逼法:对于每个元素,我们在其之后的元素中设置左右指针,分别指向紧挨着这个元素的下一个元素和数组的最后一个元素。如果当前指针元素之和小于0,则移动左指针以增加总和;如果总和大于0,则移动右指针以减少总和。
  4. 避免重复:跳过重复的元素,以避免重复的三元组。

解题关键:排序 + 两头夹逼法 + 跳过重复元素

Java解法

下面是使用Java语言的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 排序
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length && nums[i] <= 0; ++i) {
// 跳过重复值
if (i == 0 || nums[i - 1] != nums[i]) {
resolve(nums, i, result);
}
}
return result;
}

void resolve(int[] nums, int i, List<List<Integer>> result) {
// 双指针两头夹逼
int lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
++lo;
} else if (sum > 0) {
--hi;
} else {
result.add(Arrays.asList(nums[i], nums[lo++], nums[hi--]));
while (lo < hi && nums[lo] == nums[lo - 1])
++lo; // 跳过重复值
}
}
}
}

解法的时间复杂度主要由排序决定,排序的时间复杂度为 O(nlogn),遍历数组和双指针搜索的时间复杂度为 O(n^2)。因此,总的时间复杂度为 O(n^2)

References


  1. 15. 三数之和. Retrieved from https://leetcode.cn/problems/3sum/ ↩︎

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/algorithm/3sum.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。