代码随想录打卡第七天

代码随想录–哈希表部分

day7 哈希表第二天

一、力扣454–两数相加Ⅱ

代码随想录题目链接：代码随想录

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 $(i,j,k,l)$能满足：
$0<=i,j,k,l<n$
$nums1[i]+nums2[j]+nums3[k]+nums4[l]==0$

最粗暴的方法就是四个for循环，时间复杂度$O(n^4)$，完全不能接受

用哈希表能怎么处理呢？把a+b+c+d拆开，分别求a+b的值，再和c+d比较，一样的话就count++

为什么是a+b和c+d呢？因为这样时间复杂度是$O(n^2)$，a和b+c+d的时间复杂度是$O(n^3)$，就慢了

所以用一个哈希map存a+b的值和该值出现的次数，再用c+d去比较

代码如下：

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> hashmap;
        for(int a : nums1)
            for(int b : nums2)
                hashmap[a + b]++;
        int count = 0;
        for(int c : nums3)
            for(int d : nums4)
                if(hashmap.find(0-(c+d)) != hashmap.end()) count += hashmap[0-(c+d)];
        return count;
    }
};

二、力扣383–赎金信

代码随想录题目链接：代码随想录

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

简单想法就是遍历ransom的词，在magazine里面找，找到就从magazine里删除，然后下一位再次找，时间复杂度$O(n^2)$

用哈希表加速搜索的话，就是把其中一个字符串做成哈希表，用另一个搜索，因为magazine的字母不能重复用，所以把它做成哈希表，让ransomNote在里面搜

题目讲了只有小写字母，所以也可以不用哈希map，用数组就行

代码如下：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) return false;
        int hashmap[26] = {0};
        for(auto & element : magazine) hashmap[element-'a']++;
        for(auto & element : ransomNote) if(--hashmap[element - 'a'] < 0) return false;
        return true;
    }
};

用哈希map也可以：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) return false;
        unordered_map<int, int> hashmap; // change to hashmap
        for(auto & element : magazine) hashmap[element-'a']++;
        for(auto & element : ransomNote) if(--hashmap[element - 'a'] < 0) return false;
        return true;
    }
};

解释一下这行，顺序分析，是先对哈希map值减一，再进行比较，小于0就return，否则继续循环

if(--hashmap[element - 'a'] < 0) return false;

三、力扣15–三数之和

代码随想录题目链接：代码随想录

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

跟上面四数相加的区别是$i,j,k$也不能重复了，用两个for循环加哈希表找到相加为0的三元组后，再进行去重，这是常规的思路

不过会超时，所以换个方法，考虑到是一个数组，所以双指针法是可以用的，先对数组重新排序，方便处理

设置三个指针，head、middle和tail，分别指向搜索区域的头部、中间、尾部，并计算其元素的和

如果大于0，说明要减小，那尾部向前，如果小于0，说明要增大，那中间向后，直到中间和尾部相遇，则头部后移，继续循环

代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for(int head = 0; head < nums.size(); head++)
        {
            if(nums[head] > 0) break;
            int middle = head + 1;
            int tail = nums.size() - 1;
            if(head > 0 && nums[head] == nums[head-1]) continue;
            while(tail > middle)
            {
                if (nums[head] + nums[middle] + nums[tail] > 0) tail --;
                else if(nums[head] + nums[middle] + nums[tail] < 0) middle ++;
                else
                {
                    result.push_back(vector<int>{nums[head], nums[middle], nums[tail]});
                    while(tail > middle && nums[tail] == nums[tail-1]) tail--;
                    while(tail > middle && nums[middle] == nums[middle+1]) middle++;
                    tail--; middle++;
                }
            }
        }
        return result;
    }
};

去重逻辑还挺有意思的，要用

if (i > 0 && nums[i] == nums[i - 1]) continue;

去重，而不是

if (nums[i] == nums[i + 1]) continue;

是因为前者是跳过了一个“已经搜索过的同值”，而后者是跳过了一个“未搜索过的同值”

而且在相加为0的else里面很容易忘记对b和c的去重。

四、力扣18–四数之和

代码随想录题目链接：代码随想录

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
$0<=a,b,c,d<n$
$a\ne b\ne c\ne d$
$nums[a]+nums[b]+nums[c]+nums[d]==target$

跟上面的四数相加的区别在于，不是相加为0而是target，而且序号不能相同

因为要去重，所以还是用双指针法了，相当于对三数之和多一个循环，多一位固定位

target不确定，所以在开头不再是大于0就退出了，判断一下target大于0的话再退出，否则继续

代码如下：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for(int head = 0; head < nums.size(); head ++)
        {
            if(nums[head] > 0 && nums[head] > target) break;
            if(head > 0 && nums[head] == nums[head-1]) continue;
            for(int head2 = head + 1; head2 < nums.size(); head2 ++)
            {
                long sum_head = nums[head]+nums[head2];
                if(sum_head > 0 && sum_head > target) break;
                if(head2 > head + 1 && nums[head2] == nums[head2-1]) continue;   
                int middle = head2 + 1;
                int tail = nums.size() - 1;  
                while(tail > middle)
                {
                    long sum = sum_head + nums[middle] + nums[tail];
                    if (sum > target) tail --;
                    else if (sum < target) middle ++; 
                    else
                    {
                        result.push_back(
                        	vector<int>{nums[head], nums[head2],
                        				nums[middle], nums[tail]});
                        while(tail > middle && nums[tail] == nums[tail - 1]) tail --;
                        while(tail > middle && nums[middle] == nums[middle + 1]) middle ++;
                        tail --; middle++;
                    }
                }          
            }
            
        }
        return result;
    }
};

复杂倒是不复杂，就是细节比较多，要注意下。