三数之和 - 越走越远的风

欢迎关注个人公众号【好好学技术】交流学习

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

1.暴力法

老规矩，先试试暴力法然后在考虑能否优化。思路很简单就是三次for循环，获取结果。

    /**
     * 遍历三次
     * 时间复杂度O(n^3)
     *
     * @param nums 数组
     * @return 返回所有和为 0 且不重复的三元组。
     */
    private static List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        //三重for循环
        //三个且不重复的元素，所以i的最大值为 length - 2
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                for (int k = j + 1; k < length; k++) {
                    //判断三数相加之和等于0
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }

        //结果去重
        // result 结果 [[-1, 0, 1], [-1, 2, -1], [0, 1, -1]]
        //[-1, 0, 1] 和 [0, 1, -1] 是重复的，需要去重
        return distinctList(result);
    }

    /**
     * list 去重
     */
    private static List<List<Integer>> distinctList(List<List<Integer>> result) {
        List<List<Integer>> distinctList = new ArrayList<>();
        for (List<Integer> list : result) {
            //因为数组长度都为3，所以不用比较长度。只需排个序，然后使用contains方法判断即可
            //contains会遍历每个元素比较
            //list.sort(null) 如果指定的比较器为空，则此列表中的所有元素都必须实现 Comparable 接口，并且应使用元素的自然顺序。
            list.sort(null);
            System.out.println("list排序后为：" + list);
            if (!distinctList.contains(list)) {
                distinctList.add(list);
            }
        }
        return distinctList;
    }

这种方法虽然简单，但是缺点也是明显的，for循环嵌套两层for循环，时间复杂度为O(n^3)。

双指针法

双指针其实就是使用左右指针法，借鉴的是分治思想。
在数组的头尾分别放置左右指针。通过指针移动来进行搜索，指针相遇时，代表搜索结束。

下面来说说具体的思路

1.对数组进行升序排序。
2.开始遍历数组nums，如果nums[i]已经大于0，直接跳出循环，如果当前数和上一个数一样，直接continue(结果也不用去重了)
3.以当前位置i为三数中的第一个解，i+1位置为左指针(最小数)lp，数组最后一个数字为右指针(最大数)rp。
4.接下来就是对 nums[i] + nums[lp] + nums[rp] 的和sum进行判断了。
5.如果sum等于0，就找到了当前位置i的一组解。左指针右移，右指针左移，继续寻找下一组解。
6.如果sum小于0，说明左右指针中的较小数应该增大，即左指针右移。
7.如果sum大于0，说明左右指针中的较大数减少，即右指针左移。

列个表格说明一下运行过程
nums = [-1,0,1,2,-1,-4]
排序后 nums = [-4,-1,-1,0,1,2]

nums值	-4	-1	-1	0	1	2	action	goto
nums下标	0	1	2	3	4	5
	i=0	lp = 1				rp=5	-4+-1+2=-3	lp++
	i=0		lp = 2			rp=5	nums[lp] == nums[lp -1]	lp++
	i=0			lp = 3		rp=5	-4+0+2=-2	lp++
	i=0				lp = 4	rp=5	-4+1+2=-2	lp++
	i=0					lp=rp=5		i++
		i=1	lp = 2			rp=5	-1+-1+2=0	lp++,rp–
		i=1		lp = 3	rp=4		-1+0+1=0	lp++,rp–
		i=1		rp=3	lp = 4		lp > rp	i++
			i=2	lp=3		rp=5	nums[i] == nums[i - 1]	i++
				i=3	lp=4	rp=5	0+1+2=3	rp–
				i=3	rp=lp=4			i++
					i=4	lp=rp=5		i++
						i=rp=5	lp=6>rp	i++,for循环结束

好了，接下来贴上代码

    /**
     * 双指针法
     * 时间复杂度O(n^2)
     *
     * @param nums 数组
     * @return 返回所有和为 0 且不重复的三元组。
     */
    private static List<List<Integer>> threeSum2(int[] nums) {
        //结果数组
        List<List<Integer>> result = new ArrayList<>();
        //1.先排序,默认升序
        Arrays.sort(nums);

        int length = nums.length;
        //2.遍历数组
        for (int i = 0; i < length; i++) {
            //如果当前数(最小数)已经大于0，直接退出循环
            if (nums[i] > 0) {
                break;
            }
            //如果当前数已经出现过，直接跳过，也不用去重了
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //3.以i之后的最小数，定义为左指针
            int lp = i + 1;
            //3.以最后一个数(最大数)，定义为右指针
            int rp = length - 1;
            //只要左右指针不重叠，就继续移动指针
            while (lp < rp) {
                //4.当前数和左右指针的和
                int sum = nums[i] + nums[lp] + nums[rp];
                //判断sum，与0做大小对比
                if (sum == 0) {
                    //5.找到了一组解
                    result.add(Arrays.asList(nums[i], nums[lp], nums[rp]));
                    //直接移动左右指针
                    lp++;
                    rp--;
                    //如果左指针移动之后元素相同，直接跳过
                    while (lp < rp && nums[lp] == nums[lp - 1]) {
                        lp++;
                    }
                    //如果右指针移动之后元素相同，直接跳过
                    while (lp < rp && nums[rp] == nums[rp + 1]) {
                        rp--;
                    }
                } else if (sum < 0) {
                    //6.小于0，左右指针中的较小数增大，即左指针右移
                    lp++;
                } else {
                    //7.sum > 0, 左右指针中的较大数减少，即右指针左移
                    rp--;
                }
            }
        }
        return result;
    }

时间复杂度方面来思考一下。首先是外层for循环，里层其实就是左右指针的移动，所以时间复杂度为O(n^2)。

空间复杂度没有用到任何附加的数据结构，所以空间复杂度为O(1)。

源码地址

https://github.com/fandf/algorithm/blob/master/src/main/java/com/fandf/algorithm/ThreeSum.java

最后

千里之，行始于足下，每天坚持一点

如果大家有更好的解法或者疑问，欢迎留言一起交流学习。