力扣算法-Day16

454. 四数相加 II

383. 赎金信

454. 四数相加 II

给你四个整数数组 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循环。

哈希表：C语言用哈希表去解决一些问题太麻烦了。只能自己动手先实现想要的数据类型。

哈希：



struct my_struct {
    int id;                    /* key */
    int val;
    UT_hash_handle hh;         /* makes this structure hashable */
};

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size){
    struct my_struct * hash = NULL;
    for(int i = 0; i < nums1Size; i++)
    {
        for(int j = 0; j < nums2Size; j++)//统计两个数组元素之和，和出现的次数，放到hash中
        {
            int k = nums1[i] + nums2[j];
            struct my_struct * s = NULL;
            HASH_FIND_INT(hash, &k, s);
            if(s == NULL)
            {
                s = (struct my_struct *)malloc(sizeof(struct my_struct));
                s->id = k;
                s->val = 1;
                HASH_ADD_INT(hash, id, s);
            }
            else
            {
                s->val++;
            }
        }
    }
    int count = 0;
    for(int i = 0; i < nums3Size; i++)//在遍历大C和大D数组，找到如果 0-(c+d) 在hash中出现过的话，就用count把hash中key对应的value也就是出现次数统计出来
    {
        for(int j = 0; j < nums4Size; j++)
        {
            int k = 0 - nums3[i] - nums4[j];
            struct my_struct * s = NULL;
            HASH_FIND_INT(hash, &k, s);
            if(s)
            {
                count += s->val;
            }
        }
    }
    return count;
}

383. 赎金信

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

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

思路：
暴力循环：

哈希表：

与“有效的字母异位词”很像，做法是相同的。不太理解的还请去看前几篇。

哈希表代码如下：

bool canConstruct(char* ransomNote, char* magazine) {
    int letter[26] = {0};
    for (int i = 0; magazine[i] != '\0'; i++) {
        letter[magazine[i] - 'a']++;
    }
    for (int i = 0; ransomNote[i] != '\0'; i++) {
        letter[ransomNote[i] - 'a']--;
        // 检查字符在ransomNote中对应位置出现的次数是否超出在magazine中出现的次数
        if (letter[ransomNote[i] - 'a'] < 0) {
            return false;
        }
    }
    return true;
}