首页 > 三数之和
头像
蘑菇睡不着
发布于 2021-09-03 14:39
+ 关注

三数之和

描述

给出一个有n个元素的数组S,S中是否有元素a,b,c满足a+b+c=0?找出数组S中所有满足条件的三元组。
注意:
三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)
解集中不能包含重复的三元组。
例如,给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)
0 <= S.length <= 1000

示例1

输入:
[0]

返回值:
[]

示例2

输入:
[-2,0,1,1,2]

返回值:
[[-2,0,2],[-2,1,1]]

示例3

输入:
[-10,0,10,20,-10,-40]

返回值:
[[-10,-10,20],[-10,0,10]]

思路

三数之和,最简单最暴力的解法就是 三重循环遍历,但是这样的时间复杂度太高了为O(n^3)。

大家看上图,其实咱们可以使用 三指针 的方式来解决这道题。

  • 将数组按照从小到大排序。
  • 先定义I、J、K 三指针,I 位于最左侧,J 位于 I 的右侧,K 位于 数组最右侧。
  • JK 分别向对方移动,当 I + J + K > 0 时,K 向左移动,反之 J 向右移动,沿途碰到符合 I + J + K = 0 记录下来。
  • JK 遍历完之后,I 向右移动,J 位于 I 的右侧,K 位于 数组最右侧。在重复上面的逻辑即可。
  • 这里面有个问题,那就是会有重复的组合,咱们遍历的时候如果碰到相邻元素相等时,可以直接跳过,这样能减少重复次数。
  • 还有一个跳出等其他细节,大家可以看下方代码注释。

AC 代码

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            if (num == null || num.length < 3) {
                return res;
            }
            // 对数组从小到大排序
            Arrays.sort(num);
            // 如果 排序后第一个(最小的)的元素 大于 0, 那说明这个数组不可能有等于 0 的三个元素。
            if (num[0] > 0) {
                return res;
            }
            int length = num.length;
            for (int i = 0; i < length; i ++) {

                // 如果相邻的两个元素相等,则直接跳过,防止重复
                if (i > 0 && num[i] == num[i - 1]) {
                    continue;
                }
                // k 是右侧指针
                int k = length - 1;
                // 这个等价于 int temp = 0 - num[i], 确定第一个元素后,去剩下的队列中寻找另外两个元素
                int temp = - num[i];
                // 从第一个元素后边开始遍历
                for (int j = i + 1; j < length; j ++) {
                    // 这个和上面一样,碰到相邻元素相等就跳过
                    if (j > i + 1 && num[j] == num[j - 1]) {
                        continue;
                    }
                    // 当右侧指针小于左侧指针,并两者之和大于 temp 时,右侧指针要左移,因为是从小到大排序的
                    while (k > j && num[k] + num[j] > temp) {
                        k --;
                    }
                    // 当 两个指针重合时,说明 b + c > -a ==> a + b + c > 0
                    // 就算是在往后遍历也只是 a + b + c 越来越大,永远不会 等于 0,因为数组是从小到大有序的
                    if (k == j) {
                        break;
                    }
                    if (num[k] + num[j] == temp) {
                        ArrayList<Integer> list = new ArrayList<Integer>();
                        list.add(num[i]);
                        list.add(num[j]);
                        list.add(num[k]);
                        res.add(list);
                    }

                }
            }
        return res;
    }
  • 时间复杂度:时间复杂度:O(N^2),N 为数组长度
  • 空间复杂度:O(log^N),这个事排序的空间复杂度。

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。

图片说明

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

热门推荐