题目链接:15. 三数之和
思路
排序 + 双指针
采用 排序 + 双指针 的方法来解决三数之和问题。首先对数组进行排序,然后通过双指针法,针对每一个固定的元素,从其后的数组部分寻找符合条件的三元组。这样能够避免重复的三元组,且利用排序的性质来优化查找效率。
解题过程
方法运用
- 排序数组:首先将数组
nums
进行升序排序,这样可以方便使用双指针法,同时也能跳过重复的元素,避免重复的三元组。 - 遍历数组:从第一个元素开始,依次固定一个数
nums[i]
,然后使用双指针法在i+1
到数组末尾之间查找两个数nums[l]
和nums[r]
,使得三者之和为0
。- 如果三者之和等于
0
,将该三元组加入结果集。 - 如果三者之和小于
0
,左指针右移以增大和。 - 如果三者之和大于
0
,右指针左移以减小和。
- 如果三者之和等于
- 跳过重复元素:为了避免重复的三元组,在遍历过程中跳过相邻相同的元素,并在更新指针时跳过重复的
nums[l]
和nums[r]
。
复杂度
- 时间复杂度: $O(n^2)$,排序的时间复杂度为 $O(n \log n)$,而双指针的查找过程在最坏情况下为 $O(n^2)$,因此总的时间复杂度为 $O(n^2)$。
- 空间复杂度: $O(1)$,除了存储结果的空间外,算法的空间开销主要用于排序,排序可以在原数组上进行,因此不需要额外空间。
Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 存储结果的列表
List<List<Integer>> res = new ArrayList<>();
// 对数组进行排序
Arrays.sort(nums);
int n = nums.length;
// 遍历数组
for (int i = 0; i < n - 2; i++) {
// 跳过重复的第一个数字
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 双指针查找
int l = i + 1, r = n - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
// 找到三元组,加入结果集
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
// 跳过重复的左边元素
while (l < r && nums[l] == nums[l + 1]) l++;
// 跳过重复的右边元素
while (l < r && nums[r] == nums[r - 1]) r--;
// 移动双指针
l++;
r--;
} else if (sum < 0) {
l++; // 左指针右移
} else {
r--; // 右指针左移
}
}
}
return res;
}
}
标签:排序,nums,重复,三数,三元组,算法,数组,随笔,指针
From: https://www.cnblogs.com/yubaibaibubai/p/18397875