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]
]
分析：
寻找三个数相加结果为0，要求结果不能重复，且从小到大的顺序排列。
先把nums数组排序一次，然后从第一个元素开始遍历到倒数第三个元素，然后转化为两数之和问题。
用lo和hi代表另外两个元素下标，看三个相加是否等于0，若等于0则加到List中去；若小于0，说明lo元素的值小了，把lo++；若大于0，说明hi元素的值大了，把hi--。
Java：
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]) {
continue;
}
int lo = i + 1, hi = nums.length - 1, sum = -nums[i];
while (lo < hi) {
if (nums[lo] + nums[hi] == sum) {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo + 1]) {
lo++;
}
while (lo < hi && nums[hi] == nums[hi - 1]) {
hi--;
}
lo++;
hi--;
} else if (nums[lo] + nums[hi] < sum) {
lo++;
} else {
hi--;
}
}
}
return res;
}
