leetcode 刷题(数组篇)15题 三数之和 (双指针)

很有意思的一道题,值得好好思考,虽然难度只有Mid,但是个人觉得不比Hard简单

题目描述

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0]
输出:[]

提示:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

解答

解法一 排序+双指针+三循环

很容易想到的是先对序列进行排序,首尾两个指针,两个指针中间采取遍历,三个循环查找所有满足条件的答案。

时间复杂度为\(O(n^3)\) 空间复杂度为 \(O(n)\)

然后一开始就疯狂说超时,结果一番修改,终于不报超时了。

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        // 对数组进行排序
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 定义一个指针,指向数组的头部,不断的去遍历每一个不重复的元素
        // 每次遍历中再定义一个指针指向尾部,不断往前遍历,判断是否存在合理的三元组
        for (int pi = 0; pi < len - 2; pi++) {            
            // 很明显如果pi对应的值都大于0了,说明后面的全是大于0,已无解了
            if (nums[pi] > 0) {break;}
            for (int pj = len - 1; pj > pi; pj--){
                // 这里的pj值小于0,也是一样的,代表这一轮已无解了直接break
                if (nums[pj] < 0) {break;}

                for (int pz = pj - 1; pz > pi; pz--) {
                    
                    if (nums[pi] + nums[pj] + nums[pz] > 0) { continue; }
                    if (nums[pi] + nums[pj] + nums[pz] < 0) { break; }

                    if (nums[pi] + nums[pj] + nums[pz] == 0){
                        List<Integer> temp = new ArrayList<Integer>();
                        temp.add(nums[pi]);
                        temp.add(nums[pz]);
                        temp.add(nums[pj]);
                        ans.add(temp);
                        // 找到就退出此循环
                        break;
                    }
                    // 走到最后一个相同元素的位置
                    while (pz > 0 && nums[pz] == nums[pz - 1]) {pz--;}
                }
                // 走到最后一个相同元素的位置
                while (pj > 0 && nums[pj] == nums[pj - 1]) {pj--;}
            } 
            // 走到最后一个相同元素的位置
            while (pi < len - 1 && nums[pi] == nums[pi + 1]) {pi++;}
        }
        return ans;
    }
}

// 执行用时: 2164 ms
// 内存消耗: 42.3 MB

不报超时了,但是时间大概就比别人多了很多很多吧

果然时间复杂度太高了,但是想了半天也不知道是为什么,然后去看教程,教程说能将三循环优化成双循环。

一看代码还是三循环,人傻了反正是。

虽然没懂为什么for改成while起作用了,但是直接动手改写我最后的一层循环。

写着写着就悟了。。。果然实践出真知

直接上代码吧

解法二 排序+双指针+双循环

时间复杂度\(O(n^2)\)

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        // 对数组进行排序
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 定义一个指针,指向数组的头部,不断的去遍历每一个不重复的元素
        // 每次遍历中再定义一个指针指向尾部,不断往前遍历,判断是否存在合理的三元组
        for (int pi = 0; pi < len - 2; pi++) {            
            // pi指向的元素如果大于0,后面无解,直接返回
            if (nums[pi] > 0) {return ans;}
            int pz = pi + 1;
            for (int pj = len - 1; pj > pi; pj--){
                // pj指向的元素如果都小于0,说明剩余区域全部为零了,直接break
                // pz指向大于pj时说明无解了
                if (nums[pj] < 0 || pz >= pj) {break;}
                // 更新pz
                while (pz < pj && nums[pi] + nums[pj] + nums[pz] < 0) {
                    pz++;
                }
                // 记录pz如果合理
                if (pz < pj && nums[pi] + nums[pj] + nums[pz] == 0){
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(nums[pi]);
                    temp.add(nums[pz]);
                    temp.add(nums[pj]);
                    ans.add(temp);
                }
                // 走到最后一个相同元素的位置
                while (pj > 0 && nums[pj] == nums[pj - 1]) {pj--;}
            } 
            // 走到最后一个相同元素的位置
            while (pi < len - 1 && nums[pi] == nums[pi + 1]) {pi++;}
        }
        return ans;
    }
}

// 执行用时: 24 ms
// 内存消耗: 42.8 MB

这速度反正快了很多很多吧

why?

首先说明,数组按照从小到大的顺序排序,

我们最外层的循环是遍历指向数组头的指针,Head

第二层的循环是遍历指向数组尾的指针,Tail

第三层的循环是两个首尾指针中间的区域,Mid

对于一个Head,我们的尾指针Tail 将会从最后一个元素慢慢往前遍历至头元素的前一个元素。

假如此时 Head = \(n\), Tail = \(m\),\(n<m\),如果找到一个Mid =\(x\), \(n<x<m\)

满足条件 \(nums[n] + nums[x] +nums[m] = 0\)

那么此时Tail更新为\(m-1\),那么我们第三层循环的Mid指针需要重新从\(n+1\)开始遍历吗?

答案是不需要。

为什么?

此时有 \(nums[n] + nums[x] +nums[m] = 0, nums[m-1]<nums[m]\)

所以不难推出 \(nums[n]+nums[x]+nums[m-1]<0\)

因此\(x\)左边的值都只会使不等式小于0,我们只需要从\(x\)往右开始遍历Mid就可以了。

说到这里,可以发现Mid指针,在Head指针固定的情况下,只会更新小于len次,len为数组的长度。

也就是说当Head=\(n\)时,

Mid指针只会遍历小于\(length(nums)-n\)次,

而Tail指针,也是遍历小于\(length(nums)-n\)次

分配下来,Tail的一次循环Mid更新的次数是常数项。而在某些时刻Mid会直接大于Tail,就直接退出内层循环。

因此第三层循环虽然是存在,但是在第二层循环的指针固定的情况下,只会循环常数项次,至此第三层循环由\(O(n)\)被优化至\(O(1)\)

上一篇:通过枚举实现单例、策略模式


下一篇:Codeforces Round #635 (Div. 2) 题解(A.B.C.D)