平武建站

【哈希进阶】-创新互联

题目：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元起，快前往官网查看详情吧


分享名称：【哈希进阶】-创新互联
网页URL：http://pwwzsj.com/article/jgdpi.html

其他资讯