1.算法题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
2.算法思路
- 暴力法：遍历所有可能的组合，时间复杂度太高 O(n^3)；
- 排序+双指针：由于要去重，所以先把无序数组排序为有序数组 Arrays.sort(nums)，时间复杂度为 O(nlogn)；需要计算3个数的和，可以先固定第一个数，数组索引 为 i，再定义两个索引指针 left 和 right，在剩余数组区间的两端，记录满足 nums[i] + nums[left] + nums[right] = 0 的组合，并对三个位置的数分别去重，具体去重逻辑可以参考算法实现的代码；时间复杂度为 O(n^2)，其中循环遍历第一个数的复杂度是 O(n)，双指针时间复杂度为 O(n)；
3.算法代码
根据“排序+双指针”算法思路编写的算法代码如下：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
if (nums == null || nums.length < 3) {
return lists;
}
Arrays.sort(nums); // 1.排序
System.out.println("sort: ");
for (int i = 0; i < nums.length - 2; i ++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // 2.第一个元素去重
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
lists.add(Arrays.asList(nums[i], nums[left], nums[right]));
System.out.println("i: " + nums[i] + " left: " + nums[left] + " right: " + nums[right]);
while (left < right && nums[left] == nums[left + 1]) { // 3.第二个元素去重
left ++;
}
while (left < right && nums[right] == nums[right - 1]) { // 4.第三个元素去重
right --;
}
left ++;
} else if (sum < 0) {
left ++;
} else {
right --;
}
}
}
return lists;
}
4.总结
扩展问题：leecode16 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
借鉴“排序+双指针”的算法思路编写的算法实现代码如下：
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return 0;
}
Arrays.sort(nums); // 1.排序
int sum = nums[0] + nums[1] + nums[2];
int differ = Math.abs(sum - target);
if (differ == 0) {
return sum;
}
for (int i = 0; i < nums.length - 2; i ++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // 2.第一个元素去重
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int tmp = nums[i] + nums[left] + nums[right];
if (tmp == target) {
return tmp;
}
if (Math.abs(tmp - target) < differ) {
differ = Math.abs(tmp - target);
sum = tmp;
}
if (tmp < target) {
left ++;
} else {
right --;
}
}
}
return sum;
}
如果你有疑问或更好的算法思路，欢迎留言交流！！！
如果感觉我的文章对您有所帮助，麻烦动动小手给个喜欢，谢谢！！！
