三数之和
题目叙述：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解题思路：
先将小于和大于，等于0的个数统计下来并将最大值和最小值找出来，最小值小于0，最大值大于0，如果有三个0可组成一组解，我们解的最小值应该>= -maxValue * 2,最大值>= -minValue * 2这个是我们有解的最大范围如果我们的最大或者最小值超过了这个将改为超过的那个，声明三个数组negs 存储不重复的负数，poses用来存储不重复的正数，map用来存储maxValue到minValue每个数出现的次数做一个映射。我们遍历负数不重复数组进行配对，这里使用正数不重复的数组也可以看个人选择，然后我们这里用 (-negs[i])>>>1即除2将正整数部分分为两个部分因为如果左边有解另一个解一定在正数数组右边，如果有一个负数解那么另一个解一定也在正数数组右边有解故从正数数组的右边用一个值去找最后一个解在map数组中是否存在。
代码实现：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums.length < 3){
return Collections.emptyList();
}
List<List<Integer>> res = new ArrayList<>();
int minValue = Integer.MAX_VALUE;
int maxValue = Integer.MIN_VALUE;
int negSize = 0;
int posSize = 0;
int zeroSize = 0;
for (int v : nums) {
if (v < minValue)
minValue = v;
if (v > maxValue)
maxValue = v;
if (v > 0)
posSize++;
else if (v < 0)
negSize++;
else
zeroSize++;
}
if (zeroSize >= 3)
res.add(Arrays.asList(0, 0, 0));
if (negSize == 0 || posSize == 0)
return res;
if (minValue * 2 + maxValue > 0)
maxValue = -minValue * 2;
else if (maxValue * 2 + minValue < 0)
minValue = -maxValue * 2;
int[] map = new int[maxValue - minValue + 1];
int[] negs = new int[negSize];
int[] poses = new int[posSize];
negSize = 0;
posSize = 0;
for (int v : nums) {
if (v >= minValue && v <= maxValue) {
if (map[v - minValue]++ == 0) {
if (v > 0)
poses[posSize++] = v;
else if (v < 0)
negs[negSize++] = v;
}
}
}
Arrays.sort(poses, 0, posSize);
Arrays.sort(negs, 0, negSize);
int basej = 0;
for (int i = negSize - 1; i >= 0; i--) {
int nv = negs[i];
int minp = (-nv) >>> 1;
while (basej < posSize && poses[basej] < minp)
basej++;
for (int j = basej; j < posSize; j++) {
int pv = poses[j];
int cv = 0 - nv - pv;
if (cv >= nv && cv <= pv) {
if (cv == nv) {
if (map[nv - minValue] > 1)
res.add(Arrays.asList(nv, nv, pv));
} else if (cv == pv) {
if (map[pv - minValue] > 1)
res.add(Arrays.asList(nv, pv, pv));
} else {
if (map[cv - minValue] > 0)
res.add(Arrays.asList(nv, cv, pv));
}
} else if (cv < nv)
break;
}
}
return res;
}
}
