一、题目描述
来源：力扣（LeetCode）
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
- 0 <= nums.length <= 3000
- -105 <= nums[i] <= 105
二、思路分析
排序后，双指针解法
先对数组进行排序，排序后 如果存在，负数在左 正数在右的分布。
- 我们定义一个指针num[i] 遍历这个排序后的数组
- 为了使三个数之和为0 那肯定同时存在负数和正数，所以num[i]确定的情况下，我们再定义两个指针(L,R)从两边开始遍历，使
L + num[i] + R == 0即为一组三元组，遍历过程中：
- 若和
大于 0，说明R太大，R左移 - 若和
小于 0，说明L太小，L右移 - 出现重复元素 跳过
- 不满足 L < R 结束
nums[i] > 0因为已经排序好，所以后面不可能有三个数加和等于0，直接返回- 数组为
null或者数组长度小于3, 直接返回
三、代码实现
class Solution { public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList(); int len = nums.length; if(nums == null || len < 3) return res; // 排序 Arrays.sort(nums); for (int i =0; i < len ; i++) { // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 if(nums[i] > 0) break; // 去重 if(i > 0 && nums[i] == nums[i-1]) continue; int L = i +1; int R = len -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--; } elseif (sum < 0) L++; elseif (sum > 0) R--; } } return res; } }
复杂度分析
时间复杂度：
网络异常，图片无法展示
|
n
是数组
nums
的长度
空间复杂度：
网络异常，图片无法展示
|
运行结果
网络异常，图片无法展示
|
总结
这道题因为和为零 必定正负同时存在，所以我们排序后，在确定一个数的情况下，使用双指针追从俩边来进行遍历查找符合条件的数字是最直接快速点的。
这道题也算是个双指针运用的变形题目吧。
