每日一道算法题——3个数字相加等于0

3位数字相加等于0

题目

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析

给出一个数组，要找出三位数相加等于0的组合，但是结果中不能包含重复的组合。
一开始我们都会想到穷举法，时间复杂度很明显是O(n^3)，那怎样才能优化我们的代码呢？

算法

1. 首先对数组进行排序。
2. 从左向右遍历数组，每次都固定一个数，然后剩下的两个数从左边与从右边向中间靠拢得到。类似于这里面的方法,具体看下面的代码。

代码

public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);//排序
    List<List<Integer>> res = new LinkedList<>(); 
for (int i = 0; i < num.length-2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
//两个指针 一个从i+1 一个从最右边 向中间靠拢
int lo = i+1, hi = num.length-1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
//跳过重复项（已经是排好序的）如：
//-5 -4 -4 -4 -1 2 3 4 9 9 9 10
//假如i=0 lo = 1 hi = 10 
//此时num[i] = -5; num[lo] = -4;num[hi] = 9;
//lo从1跳到3
while (lo < hi && num[lo] == num[lo+1]) lo++;
//hi从10跳到8
while (lo < hi && num[hi] == num[hi-1]) hi--;

//lo与hi同时变化的原因：
//只变化一个一定不满足num[lo] + num[hi] == sum
//所以两个都变化能够减少一次无用的比较
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
else hi--;
           }
        }
    }
return res;
    }

时间复杂度为O(n^2)，改善了很多。