RELATEED CONSULTING
相关咨询
选择下列产品马上在线沟通
服务时间:8:30-17:00
你可能遇到了下面的问题
关闭右侧工具栏

新闻中心

这里有您想知道的互联网营销解决方案
【哈希进阶】-创新互联

题目:454. 四数相加 II

创新互联公司是一家专注于成都网站制作、成都网站建设与策划设计,阿瓦提网站建设哪家好?创新互联公司做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:阿瓦提等地区。阿瓦提做网站价格咨询:18980820575

题意:给了 4 个数组,查询 4 个数 之和等于0的四元组的个 

思路1 :暴力 四层 for 循环 —— O(n^{4})

思路2 :哈希法 —— O(n^{2})

我们把前两个数组当成第一组,后两个数组当成第二组,遍历 第一组 ,将任意两个元素的和出现的次数存到map中;

遍历第二组,在第二组找有没有符合 s2 = (0 - (nums[i] + nums[j]) ) ,如果有 就将 count 加 s2 出现的次数,最后返回count 即可

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
        unordered_mapres;
        int s1 = 0;
        int count = 0;
        for(int i = 0; i< nums1.size(); i++) {
            for(int j = 0; j< nums2.size(); j++) {
                s1 = nums1[i] + nums2[j];
                res[s1]++;
            }
        }
        int s2 = 0;
        for (int i = 0; i< nums3.size(); i++) {
            for (int j = 0; j< nums4.size(); j++) {
                s2 = (0 - (nums3[i] + nums4[j]));
                if(res.find(s2) != res.end()){
                    count += res[s2];
                }
            }
        }
        return count;
    }
};

1.为什么用哈希?

哈希是可以在最快时间查找一个数是否在集合中出现过

本题 我们 查找 s2 = (0 - (nums[i] + nums[j]) ) 是否在 集合中出现过

2.为什么用map哈希?

首先,因为本题数值范围不确定,用数组哈希映射浪费空间

其次,我们需要知道 数值 以及 数值出现的次数,这就需要 key value 结构,而set 不满足条件,因此,只能用map 做哈希,key 存放的是 第一组 遍历每一次的数值和, value 存的是出现的次数

3.最后是 count += 1 还是 count += res[s2]?

是 count += res[s2], 我们是要加 这个值出现的次数,也就是value 值

题目:383. 赎金信 

题意: 给两个字符串,判断 一个字符串是否可以由另一个字符串构成

思路1:暴力 —— O(n^{2}

两层for循环遍历,有相同的字符,ransomNote 就删除掉对应的字符,最后判断 ransomNote字符串的长度,等于 0 说明 magazine 可以 构成 ransomNote ;

注意:要先循环 magazine字符串,第一次暴力写成先循环 ransomNote,没Ac,因为是在magazine 中找到能 构成 ransomNote 的字符

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 (ransomNote[j] == magazine[i]) {
                    ransomNote.erase(ransomNote.begin()+j);
                     //erase函数 是删掉 括号范围内中间的数据
                }
            }
        }

        if(ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};

思路2:哈希 —— O(n) 

这道题和242.有效的字母异位词相似,这里我们需要假设两个字符串所有字母都是小写,然后就可以用数组来哈希,因为是判断后者是否可以构成前者,所以我们让后者(也就是magazine字符串)中出现的字母 次数 ++,而前者(也就是ransomNote 字符串)出现的字母 --,最后判断条件是res[i]< 0 ,表示 ransomNote  中有 magazine 没有的字母,返回false

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int res[26] = {0};
        //这个条件第一次写没有加,但同样Ac了
        if (ransomNote.size() >magazine.size()) {
            return false;
        }
        for(int i = 0; i< magazine.size(); i++) {
            res[magazine[i] - 'a']++;
        }
        for(int i = 0; i< ransomNote.size(); i++){
            res[ransomNote[i] - 'a']--;
        }
        for (int i = 0; i< 26; i++) {
            if(res[i]< 0) {
                return false;
            }
        }
        return true;
    }
};

题目:三数之和

题意:给定一个数组,在数组里面找到三个数,是他们的和等于0,返回三个数的数值,要去重

思路1:哈希(较麻烦,因为 去重细节不好处理)

两层for循环就可以确定 a 和b 的数值了,可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过,但是我题目中说的不可以包含重复的三元组。

把符合条件的三元组放进vector中,然后再去重,这样是非常费时的,很容易超时

思路2:双指针——O(n^{2}

这道题,双指针的思路很容易理解,难在去重;

双指针思路:因为题目中要求返回的是数值,而不是下标索引,所以我们可以对数组进行排序。排序后便于我们进行双指针的操作,初始 让 left 指针指向 i 的下一下位置 ,right 指针指向数组最后一个元素,开始进行条件判断 nums[i] + nums[left] + nums[right] >0,说明我们的范围大了,要缩小,因此 right--; 以此类推,nums[i] + nums[left] + nums[right]< 0, left++;

nums[i] + nums[left] + nums[right] = 0,说明找到符合条件的一组三元组,放到我们的答案数组中;找到后,就要让两个指针同时向内收缩,即 left++ ,right--;

关于去重:

a 的去重:a 如果重复了怎么办,a是nums里遍历的元素,那么应该直接跳过去

首先,因为数组是有序的 ,如果第一个数就大于0,则直接返回答案数组;

然后,nums[i] == nums [i - 1] 和 nums[i] == nums[i + 1] 这两种写法是有区别,nums[i] == nums [i - 1]是判断当前元素和前一个元素是否相等,符合a的去重; nums[i] == nums[i + 1]是判断当前元素和后一个元素是否相等,而我们后一个元素是nums[left],即如果这样写,我们就是在三元组内部去重,不符合题意,题目只说要不重复的三元组,但三元组内部的元素可以重复;可以 以 {-1,-1,2}  

b,c的去重:去重条件写在哪里? 要写在收获一组答案后再去重。

去重b:    right >left && nums[left] == nums[left + 1]

去重c : right >left && nums[right] == nums[right - 1]

例如 数据 {-1,0,0,0,1,1,1} 可以得到一组答案 {-1,0,1},此时left++, right--;此时得到的答案{-1,0,1} 因此要对b,c去重

class Solution {
public:
    vector>threeSum(vector& nums) {
        vector>res;
        sort(nums.begin(),nums.end());
        for(int i = 0; i< nums.size(); i++){
            if(nums[0] >0) {
                return res;
            }
            if(i >0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            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 {
                    res.push_back({nums[i], nums[left],nums[right]});
                    while(right >left && nums[right] == nums[right -1]) right--;
                    while(right >left && nums[left] == nums[left+1]) left++;
                    left++;
                    right--;
                }
                
            }
            
        }
        return res;
    }
};

题目:四数之和

题意:给定一个数组,求出数组中四数相加等于 target 的四元组,要去重 

思路:双指针——O(n^{3}

这道题和三数之和思路一样,只不过多了一层for循环,去重操作也是一样的,不过注意一下b的去重, 不是j >0 而是 j >i + 1;另外在标答中还有剪枝的操作,在这里并没有写出;另外双指针里面判断四个数相加时要转换成long 否则会溢出

class Solution {
public:
    vector>fourSum(vector& nums, int target) {
        vector>res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i< nums.size(); i++) {
            if(i >0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j< nums.size(); j++) {
                if (j >i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = nums.size() - 1;
                while(left< right) {
                    if((long)nums[i] + nums[j] + nums[left] + nums[right]< target) left++;
                    else if((long)nums[i] + nums[j] + nums[left] + nums[right] >target) right--;
                    else{
                        res.push_back({nums[i], nums[j], 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 res;
    }
};

剪枝操作:

class Solution {
public:
    vector>fourSum(vector& nums, int target) {
        vector>res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i< nums.size(); i++) {
            //剪枝 注意是正数的时候,两个正数相加越来越大,而两个负数相加则越来越小
            if(nums[i] >0 && target >0 && nums[i] >target) break;
            //去重
            if(i >0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j< nums.size(); j++) {
                //剪枝
                if(nums[i] + nums[j] >0 && nums[i] + nums[j] >target) break;
                //去重
                if (j >i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = nums.size() - 1;
                while(left< right) {
                    if((long)nums[i] + nums[j] + nums[left] + nums[right]< target) left++;
                    else if((long)nums[i] + nums[j] + nums[left] + nums[right] >target) right--;
                    else{
                        res.push_back({nums[i], nums[j], 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 res;
    }
};

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站名称:【哈希进阶】-创新互联
网站链接:http://lswzjz.com/article/jgdpi.html