题目:三数之和
要求:给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如 :
输入:[-1, 0, 1, 2, -1, -4],
输出:[[-1, 0, 1],[-1, -1, 2]]
解题思路:
- 对给定的数组排序,再使用双指针找出与当前数相加和为0的数
- 对于已经排序的数组而言,在0之和不会再有与之相加和为0的两个数
- 在遍历中,应判断当前数、左指针和右指针的下一位是否与当前相等,避免出现重复解
题解代码如下:
class Solution {
private List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (null == nums || nums.length < 3) {
return result;
}
// 排序
Arrays.sort(nums);
int len = nums.length;
for (int i = 0; i < len; i++) {
int temp = nums[i];
// 对于当前已排好序的数组来说,0后面的数字不可能出现三个数相加等于0
if (temp > 0) {
return result;
}
// 跳过重复元素,可以避免出现重复解
if (i > 0 && temp == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
int leftNum = nums[left];
int rightNum = nums[right];
int sum = temp + leftNum + rightNum;
if (sum == 0) {
result.add(Arrays.asList(temp, leftNum, rightNum));
// 如果当前左指针与右指针是否和下一位相同,去除重复解
while (left < right && leftNum == nums[left + 1]) {
left ++;
}
while (left < right && rightNum == nums[right - 1]) {
right --;
}
left ++;
right --;
} else if (sum < 0) {
left ++;
} else {
right --;
}
}
}
return result;
}
}