454.四数相加II , 383. 赎金信 ,15. 三数之和 , 18. 四数之和

简介: 1. **454. 四数相加II**:通过哈希表优化暴力解法,将问题分为两部分处理,时间复杂度从O(n^4)降至O(n^2)。 2. **383. 赎金信**:利用数组统计字符频率,判断子串是否能由母串构成,时间复杂度为O(n)。 3. **15. 三数之和**:借助排序与双指针技巧,将三重循环优化至双重循环,时间复杂度为O(n^2)。 4. **18. 四数之和**:在三数之和的基础上扩展,增加一层循环并结合剪枝操作,避免重复解,时间复杂度仍为O(n^3)。 这些题目展示了哈希表、双指针和排序等常用算法技巧的应用,适合巩固基础与提升解题能力。

题目:454.四数相加II  

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

0 <= i, j, k, l < n

nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1:

输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

输出:2

解释:

两个元组如下:

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2:

输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]

输出:1

 提示:

n == nums1.length

n == nums2.length

n == nums3.length

n == nums4.length

1 <= n <= 200

-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

通过次数204,710提交次数319,002

思考历程与知识点:  

如果day06的那几个哈希题目看了的话,

今天day07应该不会再用O(n^4),也就是四个for去做这道题了吧哈哈哈。

题目要求找A[i] + B[j] + C[k] + D[l] = 0,我们同样可以先求部分和,再通过结果为0来反推查找。

把四个数组分为两队,A和B分为一队,C和D分为一队。

第一步:

      先求出A[ ]和B[ ]数组的每一位成员的和,相当于任意两两配对,复杂度O(n^2), 并且同时记录这个和出现的次数。用一个k数组就可以搞定。

k[ A[ i ]+B[ j ] ]++;//下标也就是为两数的和,里面存的是这两数和出现的次数)

  第二步:

       同上一步一样,再求出C[ ]和D[ ]数组的和。

       因为题目要求(A[ ] + B[ ])+ (C[ ] + D[ ]) = 0

       所以容易推出(A[ ] + B[ ])= 0 -   (C[ ] + D[ ])

       而(A[ ] + B[ ])我们第一步已经存了,就是k数组的下标,只要判断k是否有值就可以确定有没有这个和。

所以我们直接查找就可以了,有的话,加上出现的次数就可以了。

if (umap.find(0 - (c + d)) != umap.end()) {

                   count += umap[0 - (c + d)];

题解:

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值,value:a+b数值出现的次数
        // 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话,就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

题目: 383. 赎金信  

383. 赎金信

给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以,返回 true ;否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1:

输入:ransomNote = "a", magazine = "b"

输出:false

示例 2:

输入:ransomNote = "aa", magazine = "ab"

输出:false

示例 3:

输入:ransomNote = "aa", magazine = "aab"

输出:true

提示:

1 <= ransomNote.length, magazine.length <= 105

ransomNote 和 magazine 由小写英文字母组成

思考历程与知识点:  

这题很像day06的242. 有效的字母异位词

这题同样,开26长度的数组存次数。

输入的第一个是字符子串,第二个是母串。

先存下来母串的26个字母出现次数,然后遍历子串,每个子串字母,对应母串数量减1。

如果遍历后,母串字符数量出现负数,则证明字母不够了,没法拼出来。否则就可行。

题解:

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //add
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            // 通过recode数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote,在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符,magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

题目: 15. 三数之和  

15. 三数之和

给你一个整数数组 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

思考历程与知识点:  

用三个for自然是可以的,时间复杂度是O(N^3)。

这题如果想降时间复杂度是有点困难的,但是 是可以降到O(N^2)的。

题解:

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;
    }
};

题目: 18. 四数之和  

18. 四数之和

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

0 <= a, b, c, d < n

a、b、c 和 d 互不相同

nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1:

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

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

示例 2:

输入:nums = [2,2,2,2,2], target = 8

输出:[[2,2,2,2]]

提示:

1 <= nums.length <= 200

-109 <= nums[i] <= 109

-109 <= target <= 109

题解:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
              break; // 这里使用break,统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
 
                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
 
                        // 找到答案时,双指针同时收缩
                        right--;
                        left++;
                    }
                }
 
            }
        }
        return result;
    }
};

\

相关文章
|
2月前
|
存储 数据采集 缓存
阿里云国际代理商:海外站点图片加载慢?轻量服务器搭配 OSS+CDN 优化方案
本文由阿里云国际渠道商翼龙云撰写,详解2026出海站点性能瓶颈:轻量服务器动静资源争抢带宽致加载卡顿。提出“Lighthouse+OSS+国际CDN”动静分离架构,显著提升首屏速度、降低40%成本,并满足GDPR等海外合规要求。(239字)
|
2月前
|
Web App开发 传感器 前端开发
TikTokShop卖家的环境方案:网页后台与App端如何双轨配置与自检
TikTok环境配置需分层:个人测试用二手真机+住宅代理;小团队混合真机与指纹浏览器;规模化运营则需云手机+移动/住宅代理。核心在于网页端与App端环境必须分离且参数一致,避免因设备标识、运营商、传感器等移动端特有字段缺失导致封号。
|
SQL 数据可视化 关系型数据库
开源低代码平台推荐!10款优秀的开源低代码平台!
本文介绍了10款免费开源低代码开发平台,涵盖JeeLowCode、Ample、WaveMaker等,它们通过减少代码编写量、提供高效开发工具和灵活的定制选项,帮助企业快速构建复杂应用,加速数字化转型。各平台特点鲜明,如JeeLowCode支持微服务架构,Ample适合企业级应用,WaveMaker则适用于快速原型开发。文章详细对比了这些平台的核心功能、适用场景及推荐指数,为开发者选择合适的开发工具提供了全面指南。
|
存储 JavaScript 数据库
ToB项目身份认证AD集成(一):基于目录的用户管理、LDAP和Active Directory简述
本文介绍了基于目录的用户管理及其在企业中的应用,重点解析了LDAP协议和Active Directory服务的概念、关系及差异。通过具体的账号密码认证时序图,展示了利用LDAP协议与AD域进行用户认证的过程。总结了目录服务在现代网络环境中的重要性,并预告了后续的深入文章。
1041 2
|
存储 大数据 数据挖掘
读透《阿里巴巴数据中台实践》,其到底有什么高明之处?
最近阿里巴巴分享了《阿里巴巴数据中台实践》这个PPT(自行搜索原始文章),对于数据中台的始作俑者,还是要怀着巨大的敬意去学习的,因此仔细的研读了,希望能发现一些不一样的东西。 读这些专业的PPT,实际是非常耗时的,你需要把这些PPT外表的光鲜扒光,死抠上面的每一个字去理解底下隐藏的含义,然后跟你的已有知识体系去对比,看看是否有助于完善自己的认知,对于自己不理解的,还需要经常去检索相关的文档。
13927 58
|
编译器 C语言 C++
【C++类和对象中:解锁面向对象编程的奇妙世界】(四)
【C++类和对象中:解锁面向对象编程的奇妙世界】
227 0
【C++类和对象中:解锁面向对象编程的奇妙世界】(四)
|
网络协议 安全 Linux
ssh端口转发(跳板机)详解
如果在工作环境中,被防火墙限制了一些网络端口的使用,但是允许SSH的连接,也能够将通过ssh端口转发来进行通讯。
6233 1
ssh端口转发(跳板机)详解
|
存储 安全 编译器
【C++入门:C++世界的奇幻之旅】(下)
【C++入门:C++世界的奇幻之旅】
256 0
|
缓存 Java Linux
Spring框架中的@Conditional系列注解
Spring框架中的@Conditional系列注解
729 0