LeetCode日记–15.3sum

发布于 2020-09-19  118 次阅读


碎碎念:这是不知道多少天以前的题目了,总算是有空写一下了。

题目如下:

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 that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

官方题解思路:(我太菜了没想出来)

这题乍一看和1.Two Sum 有点类似,但其实做法思路完全不同。(我自己就是陷在那一题的题解思路中,想要用递归分成两个TwoSum来解决,百思不得其解)。

首先题目的要求是三个数之和为0,那么可以预见到,满足题目条件的数字组合之中必然既有正数也有负数。

同时,题目要求中还说到“must not contain duplicate triples”,那么如果我们仅仅是O(n^3)遍历后,还不得不使用哈希表进行去重操作。

那么,这时候我们结合前面说的两点或许可以想到一个方法进行去重——在结果数字组合的三个数字(a,b,c)中,我们必须有:a≤b≤c,且a≤0,c≥0。

如此一来就会有种茅塞顿开的感觉了(并不)。既然我们要求结果数组有递增关系,那么我们可以先对数组进行排序,然后再使用三个while进行暴力迭代查找(查找时必须保证数字的大小顺序)。但是此时时间复杂度仍然是O(n^3),毕竟只是减掉了去重的时间开销。

这时我们再想,对于给定负数a,有a+b+c=0,则b+c=-a,也就是说b与c的和是一定的,这就意味着当b增大的时候,c必须减小;b减小时,c必须增大。同时,b、c之间又有严格的大小关系。那么,这是不是非常像我们之前经常练习的双指针问题,b的值是左指针,c的值是右指针,对于每个给定的a值,我们右移左指针,左移右指针,试图找到满足b+c=-a的数字组合。

这样一来,三层循环的最内两层就通过双指针思想变成了一趟遍历,也就把时间复杂度从O(n^3)变成了O(n^2)。

图示来自GitHub项目LeetCodeAnimation

说了这么多,我们来看看代码实现吧!(当时自己写的没存下来,只能用官方的代码了)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合,随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

总之,这道题还是非常经典非常棒的一道题呢!我hin喜欢:)


你好哇!欢迎来到雷公马碎碎念的地方:)