我在代码随想录|写代码Day11之双指针-三数之和,四数之和,N数之和篇

发布时间:2024年01月20日

博主介绍: 27dCnc
专题 : 数据结构帮助小白快速入门
👍👍👍👍👍👍👍👍👍👍👍👍
☆*: .。. o(≧▽≦)o .。.:*☆

三数之和

题目
在这里插入图片描述

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
       int n = nums.size();
       sort(nums.begin(),nums.end());
       vector<vector<int>>ans;
       for(int fist = 0;fist<n;fist++){
           if(fist>0&&nums[fist]==nums[fist-1]){
               continue;//剪支减少重复情况
           }
           //c对应的指针指向数组最右端
           int third = n-1;
           int target=-nums[fist];
           //枚举b
           for(int second = fist+1;second<n;second++){
               //需要和上次枚举数不相同
               if(second>fist+1&&nums[second] == nums[second-1]){
                   continue;
               }
               //需要保证b指针在c指针的左侧
               while(second<third&&nums[second]+nums[third]>target){
                   third--;
               }
               //如果指针重合,随b的后续增加
               if(second == third){
                   break;
               }
               if(nums[second]+nums[third] == target){
                   ans.push_back({nums[fist],nums[second],nums[third]});
               }
           }
       }
       return ans;
    }
};

思路 :

哈希解法

两层for循环就可以确定 a 和b 的数值了,可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过,其实这个思路是正确的,但是我们有一个非常棘手的问题,就是题目中说的不可以包含重复的三元组。
把符合条件的三元组放进vector中,然后再去重,这样是非常费时的,很容易超时,也是这道题目通过率如此之低的根源所在。去重的过程不好处理,有很多小细节
时间复杂度可以做到O(n^2),但还是比较费时的,因为不好做剪枝操作。

双指针法

其实这道题目使用哈希法并不十分合适,因为在去重的操作中有很多细节需要注意,在面试中很难直接写出没有bug的代码。
而且使用哈希法 在使用两层for循环的时候,能做的剪枝操作很有限,虽然时间复杂度是O(n^2),也是可以在leetcode上通过,但是程序的执行时间依然比较长 。
接下来我来介绍另一个解法:双指针法,这道题目使用双指针法 要比哈希法高效一些,那么来讲解一下具体实现的思路。

15.三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重a方法,将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重a方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后,对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时,双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

思考:

既然三数之和可以使用双指针法,我们之前讲过的1.两数之和 (opens new window),可不可以使用双指针法呢?

如果不能,题意如何更改就可以使用双指针法呢? 大家留言说出自己的想法吧!

两数之和 就不能使用双指针法,因为1.两数之和 (opens new window)要求返回的是索引下标, 而双指针法一定要排序,一旦排序之后原数组的索引就被改变了。

如果1.两数之和 (opens new window)要求返回的是数值的话,就可以使用双指针法了。

四数之和

题目
在这里插入图片描述

思路

四数之和,和15.三数之和 (opens new window)是一个思路,都是使用双指针法, 基本解法就是在15.三数之和 (opens new window)的基础上再套一层for循环。

但是有一些细节需要注意,例如: 不要判断nums[k] > target 就返回了,三数之和 可以通过 nums[i] > 0 就返回了,因为 0 已经是确定的数了,四数之和这道题目 target是任意值。比如:数组是[-4, -3, -2, -1],target是-10,不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝,逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

15.三数之和 (opens new window)的双指针解法是一层for循环num[i]为确定值,然后循环内有left和right下标作为双指针,找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值,依然是循环内有left和right下标作为双指针,找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况,三数之和的时间复杂度是O(n2),四数之和的时间复杂度是O(n3) 。

那么一样的道理,五数之和、六数之和等等都采用这种解法。

对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n3)的解法,降为O(n2)的解法,四数之和的双指针解法就是将原本暴力O(n4)的解法,降为O(n3)的解法。

之前我们讲过哈希表的经典题目:454.四数相加II (opens new window),相对于本题简单很多,因为本题是要求在一个集合中找出四个数相加等于target,同时四元组不能重复。

而454.四数相加II (opens new window)是四个独立的数组,只要找到A[i] + B[j] + C[k] + D[l] = 0就可以,不用考虑有重复的四个元素相加等于0的情况,所以相对于本题还是简单了不少!

我们来回顾一下,几道题目使用了双指针法。

双指针法将时间复杂度:O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级,题目如下:

  • 27.移除元素

  • 15.三数之和

  • 18.四数之和
    链表相关双指针题目:

  • 206.反转链表

  • 19.删除链表的倒数第N个节点

  • 面试题 02.07. 链表相交

  • 142题.环形链表II
    双指针法在字符串题目中还有很多应用

代码

class Solution {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置,pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时,分隔结束
            // 判断第四段子字符串是否合法,如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法,直接结束本层循环
        }
    }
    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};
  • 时间复杂度: O(3^4),IP地址最多包含4个数字,每个数字最多有3种可能的分割方式,则搜索树的最大深度为4
  • 每个节点最多有3个子节点。
  • 空间复杂度: O(n)

补充
二级剪枝的部分:

if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
    break;
}

可以优化为:

if (nums[k] + nums[i] > target && nums[i] >= 0) {
    break;
}

因为只要 nums[k] + nums[i] > target,那么 nums[i] 后面的数都是正数的话,就一定 不符合条件了。

不过这种剪枝 其实有点 小绕,大家能够理解 文章给的完整代码的剪枝 就够了。

N数之和篇

在哈希表:解决了两数之和,那么能解决三数之和么? (opens new window)中,讲到使用哈希法可以解决1.两数之和的问题

其实使用双指针也可以解决1.两数之和的问题,只不过1.两数之和求的是两个元素的下标,没法用双指针,如果改成求具体两个元素的数值就可以了,大家可以尝试用双指针做一个leetcode上两数之和的题目,就可以体会到我说的意思了。

使用了哈希法解决了两数之和,但是哈希法并不使用于三数之和!

使用哈希法的过程中要把符合条件的三元组放进vector中,然后在去去重,这样是非常费时的,很容易超时,也是三数之和通过率如此之低的根源所在。

去重的过程不好处理,有很多小细节,如果在面试中很难想到位。

时间复杂度可以做到O(n^2),但还是比较费时的,因为不好做剪枝操作。

所以这道题目使用双指针法才是最为合适的,用双指针做这道题目才能就能真正体会到,通过前后两个指针不算向中间逼近,在一个for循环下完成两个for循环的工作。

只用双指针法时间复杂度为O(n2),但比哈希法的O(n2)效率高得多,哈希法在使用两层for循环的时候,能做的剪枝操作很有限。

在双指针法:一样的道理,能解决四数之和 (opens new window)中,讲到了四数之和,其实思路是一样的,在三数之和的基础上再套一层for循环,依然是使用双指针法。

对于三数之和使用双指针法就是将原本暴力O(n3)的解法,降为O(n2)的解法,四数之和的双指针解法就是将原本暴力O(n^4) 的解法,降为O(n^3)的解法。

同样的道理,五数之和,n数之和都是在这个基础上累加。

🔥如果此文对你有帮助的话,欢迎💗关注、👍点赞、?收藏、??评论,支持一下博主~

文章来源:https://blog.csdn.net/2303_79299383/article/details/135713273
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。