算法训练day7: LeetCode454.383.15.18

454.四数相加

题目

454. 四数相加 II - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

class Solution
{
public:
    int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
    {
        unordered_map<int, int> umap; // key存数值，value存出现次数
        for (int a : nums1)
        {
            for (int b : nums2)
            {
                umap[a + b]++;
            }
        }
        int count = 0;
        for (int c : nums3)
        {
            for (int d : nums4)
            {
                if (umap.find(0 - (c + d)) != umap.end())
                {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

刚看没什么想法，后来意识到和昨天的那道题类似。

383.赎金信

题目

383. 赎金信 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

因为只有26个小写字母，使用数组哈希表。
还有目标串比来源串长的情况

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