三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件
且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
我的解答：
第一版：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
boolean needAdd = true;
boolean hasZore = false;
int length = nums.length;
for (int i = 0; i < length; i++) {
for (int j = i +1; j <length; j++){
for (int k = j + 1; k < length ; k++ ){
if (nums[i] + nums[j] + nums[k] == 0) {
// long l = System.nanoTime();
needAdd = true;
if (result.size() == 0) {
List<Integer> integers = Arrays.asList(nums[i], nums[j], nums[k]);
// integers.sort((o1, o2) -> o1 > o2 ? -1 : 1);
if (nums[i] ==nums[j] &&nums[j] == nums[k]) {
hasZore = true;
}
result.add(integers);
}else {
for (List list : result) {
if (list.contains(nums[i]) && list.contains(nums[j]) &&list.contains(nums[k])
) {
// list.retainAll()
needAdd = false;
if (nums[i] ==nums[j] && nums[j]== nums[k] && !hasZore) {
needAdd = true;
}
}
}
if (needAdd) {
if (nums[i] ==nums[j] &&nums[j] == nums[k]) {
hasZore = true;
}
result.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
}
// System.out.println(System.nanoTime() - l);
}
}
}
}
return result;
}
}
写的超级复杂，超级垃圾，而且是O(n^3)的算法，3000个数据的时候，执行时间超过了leeCode 的最低标准。
第二版
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
int length = nums.length;
MaoPao(nums);
int numj,numk;
for (int i = 0; i< length; i++){
for (int j = i+1, k = length -1; j<k && j< length && k<length;){
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> integerList = Arrays.asList(nums[i], nums[j], nums[k]);
if (!result.contains(integerList)) {
result.add(integerList);
}
j++;
k--;
}else if (nums[i] + nums[j] + nums[k] >0){
numk = nums[k];
do {
k--;
}while (nums[k] >=numk && k>i);
}else {
numj = nums[j];
do {
j++;
}while (nums[j] <=numj && j<k);
}
}
}
return result;
}
public void MaoPao(int nums[]) {
if (nums ==null) {
return;
}
int len = nums.length;
int temp;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] > nums[j]) {
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
}
}
采取了别人的建议，算法复杂度O(n^2)勉强通过。首先排序，然后一个循环取i, 一个循环直接取两个数，简化了算法。里面还有一些细节优化，是我写算法学到的。后来我百度了才知道，快排比冒泡快，而且jdk 默认的Arrays.sort 方法 更快。是别人写的一个算法。突然觉得，自己弱爆了。这个三数之和的算法，就把自己难倒了。别说写的算法成为jdk 源码了。
网上最快的算法：
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;
}
}
这个算法，我看了一遍竟然没有看懂。后来边调试边看，才懂了作者的意图。
大概记录一下；
- 首先遍历一下数组，拿到最大和最小值。以及正数的个数和负数的个数以及0的个数。
- 如果有三个0，那么直接把三个0放到结果的list 里面。
- 如果正数或者负数集合里面，有一个集合是空的，说明不可能再有结果。
- 走到这一步，说明，数组里面有正数有负数。那么，最小值的2倍 （一定是负的，因为最小值一定是负责）+ 最大值大于0，说明数组中存在的最大值没有用，因为没有可能和其他任何两个数加起来等于0.这时候，理论上的最大值边界是-minValue * 2。只有在这个区间的数，才有可能加起来等于0.同理，算出理论上的最小值。
- 用了三个数组，一个正数数组，一个负数数组，一个map 用来记录比最小值大n 的数是否有。
- 排序数组
- 循环负数的数组，得到一个值，然后除以2，得到一个中间值，然后找到比这个数中间值大的位置。从这个位置往后遍历。
- 然后算出0 减去这两个数的差值是多少。如果这个差值正好等于当前的正数或者负数，那么看下这个正数或者负数的个数是不是>1 个，如果是，说明存在多个该值，那么就把该组数据放到结果里面。如果都不是，那么去看下这个差值在数组里面是否存在，如果存在返回该组合，不存在不管。
我的算法1000多毫秒，最快的是30毫秒，将近30多倍的效率。
我佛慈悲，当以不耻下问，学无止境 。