当前位置：首页 > news >正文

【代码随想录算法训练营第42期第七天 | LeetCode454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和】

news 来源：原创 2024/9/20 10:30:53

代码随想录算法训练营第42期第七天 | LeetCode454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和

一、454.四数相加II

解题代码C：

// 哈希表大小
const int HASH_SIZE = 101;typedef struct node {int val;int count;struct node *next;
} node, *HashMap;// 哈希表插入
void hash_insert(HashMap hashmap[], int val) {int idx = val < 0 ? (-val) % HASH_SIZE : val % HASH_SIZE, count = 0;node *p = hashmap[idx];while (p->next != NULL) {p = p->next;if (p->val == val) {(p->count)++;return;}}node *new = malloc(sizeof(node));new->val = val;new->count = 1;new->next = NULL;p->next = new;return;
}// 哈希表查找
int hash_search(HashMap hashmap[], int val) {int idx = val < 0 ? (-val) % HASH_SIZE : val % HASH_SIZE;node *p = hashmap[idx];while (p->next != NULL) {p = p->next;if (p->val == val) return p->count;}return 0;
}int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size){// 初始化哈希表HashMap hashmap[HASH_SIZE];for (int i = 0; i < HASH_SIZE; i++) {hashmap[i] = malloc(sizeof(node));hashmap[i]->next = NULL;}// 统计两个数组元素之和的负值和出现的次数，放到哈希表中int count = 0, num;for (int i = 0; i < nums1Size; i++) {for(int j = 0; j < nums2Size; j++) {num = - nums1[i] - nums2[j];hash_insert(hashmap, num);}}// 统计另外两个数组元素之和，查找哈希表中对应元素的出现次数，加入总次数for (int i = 0; i < nums3Size; i++) {for(int j = 0; j < nums4Size; j++) {num = nums3[i] + nums4[j];count += hash_search(hashmap, num);}}return count;
}

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

二、383. 赎金信

解题代码C：

bool canConstruct(char* ransomNote, char* magazine) {// 定义哈希映射数组int hashmap[26] = {0};// 对magazine中字符计数while (*magazine != '\0') hashmap[*magazine++ % 26]++;// 遍历ransomNote，对应的字符自减，小于0说明该字符magazine没有或不足够表示while (*ransomNote != '\0') hashmap[*ransomNote++ % 26]--;// 如果数组中存在负数，说明ransomNote不能由magazine里面的字符构成for (int i = 0; i < 26; i++) {if (hashmap[i] < 0) return false;}return true;
}

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

三、15. 三数之和

解题代码C：

//qsort辅助cmp函数
int cmp(const void* ptr1, const void* ptr2) {return *((int*)ptr1) > *((int*)ptr2);
}int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {//开辟ans数组空间int **ans = (int**)malloc(sizeof(int*) * 18000);int ansTop = 0;//若传入nums数组大小小于3，则需要返回数组大小为0if(numsSize < 3) {*returnSize = 0;return ans;}//对nums数组进行排序qsort(nums, numsSize, sizeof(int), cmp);int i;//用for循环遍历数组，结束条件为i < numsSize - 2(因为要预留左右指针的位置)for(i = 0; i < numsSize - 2; i++) {//若当前i指向元素>0，则代表left和right以及i的和大于0。直接breakif(nums[i] > 0)break;//去重：i > 0 && nums[i] == nums[i-1]if(i > 0 && nums[i] == nums[i-1])continue;//定义左指针和右指针int left = i + 1;int right = numsSize - 1;//当右指针比左指针大时进行循环while(right > left) {//求出三数之和int sum = nums[right] + nums[left] + nums[i];//若和小于0，则左指针+1（因为左指针右边的数比当前所指元素大）if(sum < 0)left++;//若和大于0，则将右指针-1else if(sum > 0)right--;//若和等于0else {//开辟一个大小为3的数组空间，存入nums[i], nums[left]和nums[right]int* arr = (int*)malloc(sizeof(int) * 3);arr[0] = nums[i];arr[1] = nums[left];arr[2] = nums[right];//将开辟数组存入ans中ans[ansTop++] = arr;//去重while(right > left && nums[right] == nums[right - 1])right--;while(left < right && nums[left] == nums[left + 1])left++;//更新左右指针left++;right--;}}}//设定返回的数组大小*returnSize = ansTop;*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);int z;for(z = 0; z < ansTop; z++) {(*returnColumnSizes)[z] = 3;}return ans;
}

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

四、18. 四数之和

解题代码C：

/* qsort */
static int cmp(const void* arg1, const void* arg2) {int a = *(int *)arg1;int b = *(int *)arg2;return (a > b);
}int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {/* 对nums数组进行排序 */qsort(nums, numsSize, sizeof(int), cmp);int **res = (int **)malloc(sizeof(int *) * 40000);int index = 0;/* k */for (int k = 0; k < numsSize - 3; k++) { /* 第一级 *//* k剪枝 */if ((nums[k] > target) && (nums[k] >= 0)) {break;}/* k去重 */if ((k > 0) && (nums[k] == nums[k - 1])) {continue;}/* i */for (int i = k + 1; i < numsSize - 2; i++) { /* 第二级 *//* i剪枝 */if ((nums[k] + nums[i] > target) && (nums[i] >= 0)) {break;}/* i去重 */if ((i > (k + 1)) && (nums[i] == nums[i - 1])) {continue;}/* left and right */int left = i + 1;int right = numsSize - 1;while (left < right) {/* 防止大数溢出 */long long val = (long long)nums[k] + nums[i] + 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[k];res_tmp[1] = nums[i];res_tmp[2] = nums[left];res_tmp[3] = nums[right];res[index++] = res_tmp;/* right去重 */while ((right > left) && (nums[right] == nums[right - 1])) {right--;}/* left去重 */while ((left < right) && (nums[left] == nums[left + 1])) {left++;}/* 更新right与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;
}