题意：给定一组整数，找出3个整数nums[i],nums[j],nums[k]，满足以下条件，三数之和等于0且i,j,k互不相同。要求返回所有不重复的组合。
思路：
- 要求组合不重复，可以先对数组从小到大排序，这样自然就做了除重。
- 一开始肯定能想到暴搜，时间复杂度是O(n3)，肯定是不能接受的。我们可以一步步做优化，首先最外层的循环可以做剪枝，跳过重复的数字。里层的双重循环，都是从小到大遍历，效率是偏低的，可以改为一个从小达到，一个从大到小。定义left和right两个指针，分别从左右往中间移动，时间复杂度从O(n2)优化到O(n)。
- 三数之和等于0可以转化成双数之和，a+b+c=0 => a+b=-c。当a+b<-c时，说明数字不够大，left需要右移，同理，a+b>-c时，right需要左移。当a+b=-c时，加入列表，然后left右移，right左移。这里还有一个剪枝，当移动后的数字和之前的相同，可以跳过，因为要求组合不重复。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
int left = i + 1;
int right = nums.length - 1;
int sum = -nums[i];
while (left < right) {
if (nums[left] + nums[right] == sum) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
res.add(temp);
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (nums[left] + nums[right] < sum) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}