题目
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
题目大意
给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。
解题思路
用 map 提前计算好任意 2 个数字之和，保存起来，可以将时间复杂度降到 O(n^2)。这一题比较麻烦的一点在于，最后输出解的时候，要求输出不重复的解。数组中同一个数字可能出现多次，同一个数字也可能使用多次，但是最后输出解的时候，不能重复。例如 [-1，-1，2] 和 [2, -1, -1]、[-1, 2, -1] 这 3 个解是重复的，即使 -1 可能出现 100 次，每次使用的 -1 的数组下标都是不同的。
这里就需要去重和排序了。map 记录每个数字出现的次数，然后对 map 的 key 数组进行排序，最后在这个排序以后的数组里面扫，找到另外 2 个数字能和自己组成 0 的组合。
代码
/**
* 双指针法，将问题转换成两数之和 + 一些去重的小技巧
* 时间复杂度：O(n^2)
* 空间复杂度：O(n)
*
* @param nums 数组
* @return 答案
*/
public List<List<Integer>> threeSum2(int[] nums) {
//非空判断
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
//初始化
List<List<Integer>> list = new ArrayList<>();
//数组排序，方便后面去重 O(nlogn)
Arrays.sort(nums);
//遍历 O(n^2)
for (int i = 0; i < nums.length; i++) {
//当一个元素与其后一个元素相同时，跳过后一个元素，也是一种去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
//目标之和
int target = -nums[i];
//定义左，右指针
int left = i + 1;
int right = nums.length - 1;
//当左指针小于右指针时，就要一直比下去
while (left < right) {
//计算左右指针之和
int sum = nums[left] + nums[right];
//符合条件放入list
if (sum == target) {
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
//当左/右指针指向的元素与后一个元素相等时，直接跳过后一个元素，继续往后走
while (left < right && nums[left] == nums[++left]) ;
while (left < right && nums[right] == nums[--right]) ;
} else if (sum < target) {
//若两数之和小于目标值，则左指针要往后移动一位
left++;
} else {
//若两数之和大于目标值，则右指针要往前移动一位
right--;
}
}
}
return list;
}