题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组
题解
排序+双指针法
思路
- 暴力解法
最容易想到的就是暴力解法，分三层进行遍历求和，假想左、中、右三个指针在数组上移动，分别代表a、b、c，并且各自位置如名称所示，左指针在最左面，右指针在最后面，中间是中指针，暴力解法如下：
左指针为最外层遍历，中指针为第二次遍历，右指针为最内侧遍历，例如左指针在数组左边界位置，中指针在左指针+1位置，右指针在中指针+1位置，这是初始位置，然后启动暴力解法，左中指针不动，右指针后移遍历。
右指针遍历到数组右边界后，中指针后移一位，右指针变为中指针+1位置，然后再开始遍历，最终经过多伦遍历后，中指针也到了数组右边界，然后下一轮左指针后移一位，再次启动三层遍历。
以上思路最容易想到，但最笨，复杂度最高。 - 排序+双指针法
数组经过排序后，最外层左指针的遍历和暴力解法一样不变，变的是中右指针的遍历，由于数组是经过排序的，排序后的数组从左至右升序，这是中右指针运用双指针法的基础。- 遍历左指针（假设左指针不动，为最外层遍历）
- 中右指针进行双指针法遍历
中指针不动，如果左、中、右加和大于0，说明等于0的结果出现在左侧（左、中指针固定，因此只能右指针左移），右指针左移，直到等于0或者小于0，如果等于0，那么此时的结果就是求解的一组解。
如果小于0，说明求解结果在右侧（左指针固定，右指针不可能再右移，因为右移后左中右加和又会大于0，因此只能是中指针右移），中指针右移，又移后再次根据左中右加和结果启动新一轮的双指针遍历：
如果加和大于0，则右指针不断左移，如果等于0就找到一组解，如果小于0，则中指针右移，直到左指针右侧的数组区域都被双指针法扫过为止。 - 中右指针法遍历后，左指针右移一位，中指针位置又变为左指针+1，右指针位置又变为数组右边界，再次启动新位置的一轮中右指针遍历
注意，左指针每次变换位置时，需要保证新旧位置的值不同，因为如果相同，那么旧位置时找到的解法，肯定和新位置时的解法是重复的（因为左指针新旧位置的值是一样的）。
同样中指针也是，左指针固定不变，中指针新旧位置值一样，那旧位置的解也同样是新位置的解，出现重复解。
代码
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 排序
Arrays.sort(nums);
// 左指针遍历
for (int left = 0; left < nums.length; left++) {
// 如果左指针数值大于0，则左、中、右指针和必定大于0，结束
if (nums[left] > 0) {
break;
}
// 左指针需要跳过重复出现的数值
if (left > 0 && nums[left] == nums[left - 1]) {
continue;
}
// 右指针，跟随左指针的变动，每次初始化为数组右边界
int right = nums.length - 1;
// 在左指针右侧遍历中指针
for (int middle = left + 1; middle < nums.length; middle++) {
// 中指针需要跳过重复出现的数值
if (middle > left + 1 && nums[middle] == nums[middle - 1]) {
continue;
}
// 左中右加和如果大于0，在左、中不变的基础上，右指针左移
while (middle < right && nums[left] + nums[middle] + nums[right] > 0) {
right--;
}
// 如果中右双指针相遇直接结束中右双指针
if (middle == right) {
break;
}
// 如果左中右加和为0，则为要找的值
if (nums[left] + nums[middle] + nums[right] == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[left]);
list.add(nums[middle]);
list.add(nums[right]);
result.add(list);
}
}
}
return result;
}
网友评论