题目1:454 四数相加Ⅱ
题目链接:454 四数相加Ⅱ
题意
4个整数数组nums1, nums2, nums3, nums4的长度均为n,有多少个元组(i,j,k,l)使得
nums[i]+nums[j]+nums[k]+nums[l]==0 (本题不包含去重的逻辑,i,j,k,l 可以相等,一组元素与一组元素之间的各个元素也可以相等)
暴力解法
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int count = 0;
for(int i=0;i<nums1.size();i++){
for(int j=0;j<nums2.size();j++){
for(int k=0;k<nums3.size();k++){
for(int l=0;l<nums4.size();l++){
if(nums1[i]+nums2[j]+nums3[k]+nums4[l]==0){
count++;
}
}
}
}
}
return count;
}
};
会报如下超时错误
map
数组的数值较大且较为分散,所以数组可以排除
将4个元素分组,分成两组(这样的时间复杂度最低O(n^2))nums1与nums2 nums3与nums4
看其中一组的元素和是否出现过,还要知道出现过的次数(value),因此使用map
unordered_map的读写效率最高
步骤
① 遍历nums1和nums2,求解nums1[i]+nums2[j]的和,将这个和及其出现的次数放到map中
② 遍历nums3和nums4,在map中查询0-(nums3[k]+nums4[l]),
如果存在key==0-(nums3[k]+nums4[l]) 就将count加上key对应的value,这点很重要,一定要加value,因为这个key可能在nums1和nums中出现多种组合,这都是满足题目要求的!!!
例如:
nums1[1]+nums1[2]=5
nums1[1]+nums1[4]=5
nums1[3]+nums2[5]=5
nums3[1]+nums4[1]=-5
这种就是nums1[i]+nums2[j]在map中存在多种组合,key==5时,对应的value==3
因此,count=count+3
单纯下标
代码文章来源地址https://www.toymoban.com/news/detail-819722.html
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> map;//定义map,存放nums1[i]+nums2[j]
int count = 0;
for(int i=0;i<nums1.size();i++){
for(int j=0;j<nums2.size();j++){
map[nums1[i]+nums2[j]]++;
}
}
for(int k=0;k<nums3.size();k++){
for(int l=0;l<nums4.size();l++){
int target = 0 - (nums3[k]+nums4[l]);
if(map.find(target)!=map.end()){
count += map[target]; //加上target(即nums[i]+nums[j])出现的次数
}
}
}
return count;
}
};
- 时间复杂度: O(n^2)
- 空间复杂度: O(n^2),最坏情况下A和B的值各不相同,相加产生的数字个数为 n^2
简便
代码
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> map;
int count = 0;
for(int a:nums1){
for(int b:nums2){
map[a+b]++;
}
}
for(int c:nums3){
for(int d:nums4){
if(map.find(0-(c+d))!=map.end()){
count += map[0-(c+d)];
}
}
}
return count;
}
};
- 时间复杂度: O(n^2)
- 空间复杂度: O(n^2),最坏情况下A和B的值各不相同,相加产生的数字个数为 n^2
以上解法和有效字母异位词比较相像,都是先遍历数组,对哈希表进行插入操作;再遍历另外的数组,在哈希表中进行查询操作
题目2:赎金信
题目链接:383 赎金信
题意
判断ransomNote字符串能否由magazine字符串中的字符组成,二者均由小写英文字母构成,但是magzine中的每个字符只能使用1次,这两点很关键
即判断ransomNote字符串中的字符是否在magazine中出现过,因此使用哈希表
数组
由于两个字符串中的元素只包含小写字母,是连续的,是有限值且有有限个,因此想到使用数组
步骤
① 一定要先遍历magazine字符串(因为是在magazine字符串中查找ransomNote中的字符是否存在),统计magazine字符串中每个字符出现的次数(每个字符只能使用1次),记录在hash数组中;
② 再遍历ransomNote字符串,在上述统计的次数的基础上,遇到相同的字符,在hash数组中对应元素做减减的操作;
③ 最后遍历hash数组,看是否有小于0的元素,若出现小于0的元素,证明ransoNote字符串中的对应该字符数量多于magazine字符串中该字符的数量,说明ransomNote字符串不能由magazine字符串中的字符组成
代码
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int hash[26] = {0};
for(int i=0;i<magazine.size();i++){
hash[magazine[i]-'a']++;
}
for(int i=0;i<ransomNote.size();i++){
hash[ransomNote[i]-'a']--;
}
for(int i=0;i<26;i++){
if(hash[i]<0){
return false;
}
}
return true;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1),hash数组的大小是常数
代码也可以这样写,hash减减后,直接判断hash中该元素是否小于0,若小于0的话,直接return false即可,就不用后面的hash元素再继续减减操作了
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int hash[26] = {0};
for(int i=0;i<magazine.size();i++){
hash[magazine[i]-'a']++;
}
for(int i=0;i<ransomNote.size();i++){
hash[ransomNote[i]-'a']--;
if(hash[ransomNote[i]-'a']<0){
return false;
}
}
return true;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1),hash数组的大小是常数
暴力解法(不推荐)
如果遇到magazine[i]==ransomNote[i],就将ransomNote中的该字符删掉,同时一定要使用break跳出这个内部for循环,因为magazine中的一个字符只能匹配ransomNote中的1个字符,如果匹配上了,那么这个字符就废了,不能再重复使用了,需要继续下一个magazine元素的循环
代码
!!!注意break的使用
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
for(int i=0;i<magazine.size();i++){
for(int j=0;j<ransomNote.size();j++){
if(magazine[i]==ransomNote[j]){
ransomNote.erase(ransomNote.begin()+j);
break;//这里一定要break,因为magazine[i]已经和ransomNote[j]匹配了,再往下让magazine[i]匹配元素不满足要求
//(magazine中的字符只能在ransomNote中使用1次),所以使用break跳出这层内部for循环,继续i++下一个magazine的元素
}
}
}
if(ransomNote.size()==0){
return true;
}else{
return false;
}
}
};
- 时间复杂度: O(n^2)
- 空间复杂度: O(1)
题目3:15 三数之和
题目链接:15 三数之和
题意
1个整数数组nums ,找出nums[i]+nums[j]+nums[k]==0的[i,j,k]的组合,其中i,j,k互不相等(意味着元素不能重复使用)一组中的nums[i],nums[j],nums[k]的组合不能和另一组中的nums[i],nums[j],nums[k]完全相同,比如:0 1 -1 和 1 0 -1这就重复了,所以需要去除一组
去重是关键
哈希法(不推荐)
使用哈希表去重细节较多
双指针法
不可以先将数组中相同的元素删除,因为可能会使得一些满足条件的组合消失,例如:2 2 -4
开始时一定要对数组进行排序
逻辑反例
例1,nums[left],nums[right]去重放置的位置
是和nums[i]一样,放在前面,还是放在while循环的最后面
例2,是先移动left,right还是先去重
这里在写代码时,产生了矛盾,当元素组合满足条件时,到底是先移动还是先去重呢?
丢掉解
重复解
例3,if(nums[i]==nums[i-1]){},{}里是i++,还是continue
想的比较单纯:遇到重复值,我跳过去,不就OK了嘛,但是事实不是这样,有可能有连续的多个重复的值,所以使用i++就产生了错误
例4,如果跳过了重复值,会不会错过一些遍历重复值过程中的组合呢
例5 nums[left] nums[right]去重逻辑里面while循环加入right>left
如果不加right<left的限制会报如下错误
代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());//记得排序
for(int i=0;i<nums.size();i++){
//nums[i]剪枝 一级剪枝
if(nums[i]>0){
return result;//这里是return result 不能return {},在此之前可能已经有结果了
//break;//这里使用break,也是一样的,直接return结果,结束这个for循环
}
//nums[i]去重 一级去重
if(i>0 && nums[i]==nums[i-1]){
continue;//继续下一次循环
//注意这里continue不能写i++,因为要是写i++的话,对于连续3个相同的数字,会算两遍,看反例3
}
int left = i + 1;
int right = nums.size() - 1;
while(right > 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]});
//去重去的是满足条件的相同的组合,因此,要放在else里面
while(right>left && nums[right]==nums[right-1]){
right--;
}
while(right>left && nums[left]==nums[left+1]){
left++;
}
left++;//一定要在去重之后再移动left和right两个指针
right--;
}
}
}
return result;
}
};
- 时间复杂度: O(n^2)
- 空间复杂度: O(1)
题目4:18 四数之和
题目链接:18 四数之和
题意
整数数组nums的长度为n,返回nums[a]+nums[b]+nums[c]+nums[d]==target的元组[nums[a],nums[b],nums[c],nums[d]],其中a,b,c,d互不相等(意味着元素不能重复使用),返回的元组不能重复,但元组内部的元素可以重复(因为数组nums中可能存在重复的元素)
双指针法
和上题三数之和一样,同样使用双指针法解决
剪枝的时候要注意,因为target可正可负可零,所以剪枝逻辑就不能像三数之和那样,直接判断nums[i]>target就行了,若target可能为负数,若nums[i]>target,若nums[i+1]还是负数,那么nums[i]+nums[i+1]<nums[i],可能会出现四数之和等于target的情况,如下例:
1) 对于一级剪枝,所以一级剪枝要确定target>0&&nums[i]>target
同样地,对于二级剪枝,也要注意这些细节,二级剪枝时,将nums[i]+nums[j]视作一个整体,与target进行判断
流程
文章来源:https://www.toymoban.com/news/detail-819722.html
代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
//一级剪枝
if(nums[i]>target && target>=0){
//if(nums[i]>target && (target>=0 || nums[i]>=0))
return result;
}
//一级去重
if(i>0 && nums[i]==nums[i-1]){
continue;
}
for(int j=i+1;j<nums.size();j++){
//二级剪枝 将nums[i]+nums[j]看作一个整体
if(nums[i]+nums[j]>target && target>=0){
//if(nums[i]+nums[j]>target && (target>=0 || nums[i]+nums[j]>=0))
break;
}
//二级去重
if(j>i+1 && nums[j]==nums[j-1]){
continue;
}
int left = j + 1;
int right = nums.size() - 1;
while(right>left){
if((long) nums[i]+nums[j]+nums[left]+nums[right]>target){
right--;
}
else if((long) nums[i]+nums[j]+nums[left]+nums[right]<target){
left++;
}
else{
result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
//nums[left] nums[right]去重
while(right>left && nums[left]==nums[left+1]){
left++;
}
while(right>left && nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}
}
}
}
return result;
}
};
- 时间复杂度: O(n^3)
- 空间复杂度: O(1)
到了这里,关于day07 四数相加Ⅱ 赎金信 三数之和 四数之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!