题目

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.

Notice
The solution set must not contain duplicate triplets.

Notice

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
 [-1, 0, 1],
 [-1, -1, 2]
]

题目大意

给定一个数组，要求在这个数组中找到3个数之和为0的所有组合。

解题思路

排序 + 双指针

大体的思路是先将给定的数组进行排序(排序的目的是实现在循环中内层的循环就不需要从比first值开始了，因为 [-1, 0, 1]、[0, -1, 1]和[0, 1, -1] 都是同一组)，接着正常分析的话，可以看出这是一个三层循环，时间复杂度是O(N³)，但是其中 [-1, 0, 1]、[0, -1, 1]和[0, 1, -1] 都是一种情况，所以后续我们需要通过哈希表来进行去重的操作。但其实是可以通过指针的方法将复杂度转化为O(N²)，因为题目要求我们实现三个数加起来为0，所以其实只要满足first=-(second+third)， 即第二重循环和第三重循环实际上是并列的关系。此时我们就可以使用双指针法，将second和third放在一层循环中。

代码

package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class D15_3Sum {

    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        //枚举
        for (int first = 0; first < n; ++first) {
            // 要求和上一次的枚举不同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // third初始值始终是最右端
            int third = n - 1;
            int target = -nums[first];
            for (int second = first + 1; second < n; second++) {
                // 需要和上一次枚举的数不相同
                if (second > first+1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                //需要保证second在third的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                //当指针重合时，结束循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }

        return ans;
    }

}

复杂度分析

* 时间复杂度：O(N²) N代表的是nums数组的长度。
* 空间复杂度：O(log(N)) 这里就是排序所需要的空间复杂度。

收获与总结

当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N²) 减少至 O(N)。为什么是 O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 bb），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。