c 还可以做网站,应届生求职网站官网,大连网站建设仟亿科技,精准营销的核心代码随想录 (programmercarl.com)
Leetcode 454. 四数相加 II
题目描述
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) #xff0c;使得 A[i] B[j] C[k] D[l] 0。
为了使问题简单化#xff0c;所有的 A, B, C, D 具有相同的长度 N#…代码随想录 (programmercarl.com)
Leetcode 454. 四数相加 II
题目描述
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) 使得 A[i] B[j] C[k] D[l] 0。
为了使问题简单化所有的 A, B, C, D 具有相同的长度 N且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间最终结果不会超过 2^31 - 1 。
例如:
输入:
A [ 1, 2]B [-2,-1]C [-1, 2]D [ 0, 2]
输出:
2
解释:
两个元组如下:
(0, 0, 0, 1) - A[0] B[0] C[0] D[1] 1 (-2) (-1) 2 0(1, 1, 0, 0) - A[1] B[1] C[0] D[0] 2 (-1) (-1) 0 0 解题思路
本题解题步骤
首先定义 一个unordered_mapkey放a和b两数之和value 放a和b两数之和出现的次数。遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中。定义int变量count用来统计 abcd 0 出现的次数。再遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就用count把map中key对应的value也就是出现次数统计出来。最后返回统计值 count 就可以了
本题乍眼一看好像和0015.三数之和 (opens new window)0018.四数之和 (opens new window)差不多其实差很多。本题是使用哈希法的经典题目而0015.三数之和 (opens new window)0018.四数之和 (opens new window)并不合适使用哈希法因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的很有多细节需要处理。而这道题目是四个独立的数组只要找到A[i] B[j] C[k] D[l] 0就可以不用考虑有重复的四个元素相加等于0的情况所以相对于题目18. 四数之和题目15.三数之和还是简单了不少 完整代码
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint,int map;// 遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中for (int a : nums1) {for (int b : nums2) {map[a b];}}int count 0; // 统计abcd 0 出现的次数// 再遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就把map中key对应的value也就是出现次数统计出来。for (int c : nums3) {for (int d : nums4) {if (map.find(0 - (c d)) ! map.end()) {count map[0 - (c d)];}}}return count;}
};
Leetcode 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 105ransomNote 和 magazine 由小写英文字母组成
解题思路
本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成但是这里需要注意两点。 第一点“为了不暴露赎金信字迹要从杂志上搜索各个需要的字母组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母这一点很重要
因为题目说只有小写字母那可以采用空间换取时间的哈希策略用一个长度为26的数组来记录magazine里字母出现的次数。然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
依然是数组在哈希法中的应用。使用map得空间消耗要比数组大 完整代码
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int recode[26] {0};if(ransomNote.size() magazine.size()) {return false;}for(int i0; iransomNote.size(); i) {recode[ransomNote[i] - a];}for(int i0; imagazine.size(); i) {recode[magazine[i] - a]--;}
// 检查 recode 数组中的每个元素。如果任何一个元素大于0这意味着 ransomNote 中有的字母在 magazine 中没有足够的数量因此无法构造 ransomNote返回 falsefor(int i0; i26; i) {if(recode[i] 0) {return false;}}return true;}
};
Leetcode 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 。 解题思路
哈希解法
两层for循环就可以确定 a 和b 的数值了可以使用哈希法来确定 0-(ab) 是否在 数组里出现过其实这个思路是正确的但是我们有一个非常棘手的问题就是题目中说的不可以包含重复的三元组。
把符合条件的三元组放进vector中然后再去重这样是非常费时的很容易超时也是这道题目通过率如此之低的根源所在。
去重的过程不好处理有很多小细节如果在面试中很难想到位。时间复杂度可以做到O(n^2)但还是比较费时的因为不好做剪枝操作。 双指针
拿nums数组来举例首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。
接下来如何移动left 和right呢 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。
如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。
时间复杂度O(n^2) 完整代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {// 定义一个二维向量 result用于存储所有满足条件的三元组vectorvectorint 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) {// 去重复逻辑如果放在这里000 的情况可能直接导致 rightleft 了从而漏掉了 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(vectorint{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;}
};
Leetcode第15题. 三数之和_leetcode——15-CSDN博客
Leetcode 18. 四数之和
Leetcode 18. 四数之和-CSDN博客
四数之和和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)就可以了
我们可以与三数之和的代码进行对比
