代码随想录第七天

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

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

思路：

本题可以使用哈希表的方法，先把nums1和nums2的和作为键放到哈希表中，然后计算它出现的次数，作为哈希表的值，然后在nums3和nums4的和中寻找与其相加等于0的数字，最终把其次数作为最终答案返回出来就是最终的答案。

解答：

struct HashNode
{
    int key;
    int value;
    struct HashNode* next;
};
struct HashTable
{
    int size;
    struct HashNode** table;
};
struct HashNode* createnode(int key,int value)
{
    struct HashNode* node = malloc(sizeof(struct HashNode));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}
int hashFuction(int key,int tablesize)
{
    return (key % tablesize + tablesize) % tablesize;
}
struct HashTable* createtable(int size) {
    struct HashTable* hashtable = malloc(sizeof(struct HashTable));
    hashtable->size = size;
    hashtable->table = malloc(sizeof(struct HashNode*) * size); 
    for (int i = 0; i < size; i++) {
        hashtable->table[i] = NULL;
    }
    return hashtable;
}
void insert(struct HashTable* hashtable,int key,int value)
{
    int hashindex = hashFuction(key,hashtable->size);
    struct HashNode* node = hashtable->table[hashindex];
     while (node != NULL) {
        if (node->key == key) {
            node->value += value;  
            return;
        }
        node = node->next;
    }
    struct HashNode* newNode = createnode(key, value);
    newNode->next = hashtable->table[hashindex];
    hashtable->table[hashindex] = newNode;
}
int search(struct HashTable* hashtable,int key)
{
    int hashindex = hashFuction(key,hashtable->size);
    struct HashNode* node = hashtable->table[hashindex];
    while(node != NULL)
    {
        if(node->key == key)
        {
            return node->value;
        }
        node = node->next;
    }
    return 0;
}
void freehash(struct HashTable* hashtable)
{
	for (int i = 0; i < hashtable->size; i++)
	{
		struct HashNode* node = hashtable->table[i];
		while (node != NULL)
		{
			struct HashNode* temp = node;
			node = node->next;
			free(temp);
		}
	}
	free(hashtable->table);
	free(hashtable);
}
int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size) {
    struct HashTable* node = createtable(10000);
    int count = 0;
    for(int i = 0;i < nums1Size;i++)
    {
        for(int j = 0;j < nums2Size;j++)
        {
            int sum = nums1[i] + nums2[j];
            insert(node,sum,1);        
        }
    }
    for(int k = 0;k < nums3Size;k++)
    {
        for(int m = 0;m < nums4Size;m++)
        {
            int sum = -(nums3[k] + nums4[m]);
            count += search(node,sum);
        }
    }
    freehash(node);
    return count;
}

注意：写哈希函数时不能像之前在用链表写哈希函数时那个函数那样写，要进行修改

int hashFuction(int key, int tablesize) {
    return (key % tablesize + tablesize) % tablesize; 
}

这么做的目的是防止里面有负数，导致结果报错。

383.赎金信

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

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

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

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

思路：

这里我们可以使用哈希表，我们把这里面的字母替换成相应的ASCII码值，然后分别建立一个数组，把ASCII码值作为下标，加上它们出现的次数，然后对比相同下标下的次数是否相同，直接求解。

解答：

bool canConstruct(char* ransomNote, char* magazine) {
    int num1 = strlen(ransomNote);
    int num2 = strlen(magazine);
    int sum1[26] = {0};
    int sum2[26] = {0};
    for(int i = 0;i < num1;i++)
    {
        sum1[ransomNote[i]-'a'] += 1;
    }
    for(int j = 0;j < num2;j++)
    {
        sum2[magazine[j]-'a'] += 1;
    }
    for(int i = 0;i < 26;i++)
    {
        if(sum1[i] > sum2[i])
        {
            return false;
        }
    }
    return true;
}

15.三数之和

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

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

思路：

这里看起来可以用哈希表，但是它不能包含重复的三元组，所以我们用哈希表的话可能会有点困难，在这里我们听取意见，使用双指针的方法来完成这道题。先使用排序算法，再使用类似二分法的思想，一个left为元素+1的位置上，一个right在最末尾的位置上，然后对于相同元素的我们直接跳过，然后一个一个对比是否为0，思路还是比较好懂，但是代码难写。

解答：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int compare(const void* num1,const void* num2)
{
    return (*(int*)num1 - *(int*)num2);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if(numsSize < 3)return NULL;
    qsort(nums,numsSize,sizeof(int),compare);
    int** result = malloc(sizeof(int*)*(numsSize*numsSize/2));
    *returnColumnSizes = malloc(sizeof(int)*(numsSize*numsSize/2));
    for(int i = 0;i < numsSize-2;i++)
    {
        if(i > 0 && nums[i] == nums[i-1])
        {
            continue;
        }
        int left = i+1;
        int right = numsSize-1;
        while(left < right)
        {
            if(nums[i] + nums[left] + nums[right] == 0)
            {
                result[*returnSize] = malloc(sizeof(int)*3);
                result[*returnSize][0] = nums[i];
                result[*returnSize][1] = nums[left];
                result[*returnSize][2] = nums[right];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
                while(left < right && nums[left] == nums[left+1])left++;
                while(left < right && nums[right] == nums[right-1])right--;
                left++;
                right--;
            }
            else if(nums[i] + nums[left] + nums[right] < 0)
            {
                left++;
            }
            else
            {
                right--;
            }
        }
    } 
    return result;
}

18.四数之和

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

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

思路：

我觉得它跟上面的三数之和差不多，都可以用双指针法，但是这个比上面的多了一个元素，所以我们需要重新定义指针的位置。与上面的思想相同，但是这次要流出后面的三个元素，同时要使用两个for循环来确定两个指针的位置，然后后面就用上面的双指针，一个left，一个right就能实现了。

解答：

int sort(const void* a,const void* b)
{
    int num1 = *(int*)a;
    int num2 = *(int*)b;
    return num1 - num2;
} 
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(nums,numsSize,sizeof(int),sort);
    int** res = malloc(sizeof(int*)*4000);
    int index = 0;
    for(int i = 0;i < numsSize-3;i++)
    {
        if(nums[i] > 0 && nums[i] > target)
        {
            break;
        }
        if(i > 0 && nums[i] == nums[i-1])
        {
            continue;
        }
        for(int j = i+1;j < numsSize-2;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 = numsSize-1;
            while(left < right)
            {
                long long val = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                 if (val > target) {
                    right--;
                } else if (val < target) {
                    left++;
                } else {
                    int *res_tmp = (int *)malloc(sizeof(int) * 4);
                    res_tmp[0] = nums[i];
                    res_tmp[1] = nums[j];
                    res_tmp[2] = nums[left];
                    res_tmp[3] = nums[right];
                    res[index++] = res_tmp;
                    while(left < right && nums[right] == nums[right-1])
                    {
                        right--;
                    }
                    while(left < right && nums[left] == nums[left+1])
                    {
                        left++;
                    }
                    left++;
                    right--;
                }
            }
        }
    }

    *returnSize = index;

    int *column = (int *)malloc(sizeof(int) * index);
    for (int i = 0; i < index; i++) {
        column[i] = 4;
    }
    *returnColumnSizes = column;
    return res;
}

反思：

这几道题都还有难度，先把大致思想弄懂，后面在复习的时候还要多多思考和理解，但是不得不说，C语言写哈希表真是不好写，还要自己手搓哈希表，真无语了。