代码随想录算法训练营第7天 | 454. 四数相加 II | 383. 赎金信 | 15. 三数之和

454. 四数相加 II

题意

找出四个数组中元素和为0的次数

解

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map;int ans = 0;for (int i : nums1) {for (int j : nums2) {map[i+j]++;}}for (int i : nums3) {for (int j : nums4) {if (map.count(-i-j)) {ans += map[-i-j];}}}return ans;}
};

383. 赎金信

题意

字符串a, 是否能用字符串b中的元素拼出来

解

#define max 1e5+10bool canConstruct(char* ransomNote, char* magazine) {int hash[10005];memset(hash, 0, sizeof(int) * 10005);for (int i = 0; magazine[i]; i++) {hash[magazine[i] - 'a']++;}for (int i = 0; ransomNote[i]; i++) {if (hash[ransomNote[i] - 'a']-- == 0) {return false;}}return true;
}

15. 三数之和

题意

一个数组, 三个元素相加等于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 cmp(const void *a, const void *b) {return *(int *)a > *(int *)b;
}int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {int **array = (int **)malloc(sizeof(int *) * 30000);int h = 0;for (int i = 0; i < 30000; i++) {array[i] = (int *)malloc(sizeof(int) * 3);}qsort(nums, numsSize, sizeof(int), cmp);for (int i = 0; i < numsSize; i++) {if (nums[i] > 0) break;if (i > 0 && nums[i] == nums[i-1]) continue;int j = i+1, k = numsSize-1;while (j < k) {if (nums[i] + nums[j] + nums[k] < 0) {j++;} else if (nums[i] + nums[j] + nums[k] > 0) {k--;} else {array[h][0] = nums[i];array[h][1] = nums[j];array[h++][2] = nums[k];while (j < k && nums[j] == nums[j+1]) j++;while (j < k && nums[k] == nums[k-1]) k--;j++;k--;}}}*returnSize = h;*returnColumnSizes = (int *)malloc(sizeof(int) * 30000);for (int i = 0; i < h; i++) {(*returnColumnSizes)[i] = 3;}return array;
}

数组要申请的大一些, 否则报内存错误

18. 四数之和

题目链接

题意

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

解

/*** 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().*/#define max 100int cmp(const void *a, const void *b) {return *(int *)a > *(int *)b;
}int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {int **array = NULL;int k = 0;array = (int **)malloc(sizeof(int *) * max);for (int i = 0; i < max; i++) {array[i] = (int *)malloc(sizeof(int) * 5);}qsort(nums, numsSize, sizeof(int), cmp);for (int i = 0; i < numsSize-3; i++) {if (i > 0 && nums[i] == nums[i-1]) continue;if ((long)nums[i] + nums[i+1] - target > -(nums[i+2] + nums[i+3])) break;if ((long)nums[i] + nums[numsSize-3] + nums[numsSize-2] + nums[numsSize-1] < target) continue;for (int j = i+1; j < numsSize-2; j++) {if (j > i+1 && nums[j] == nums[j-1]) continue;if ((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;;if ((long)nums[i] + nums[j] + nums[numsSize-1] + nums[numsSize-2] < target) continue;int n = j+1, m = numsSize-1;while (n < m) {if ((long)nums[i] + nums[j] + nums[n] + nums[m] < target) {n++;} else if ((long)nums[i] + nums[j] + nums[n] + nums[m] > target) {m--;} else {array[k][0] = nums[i];array[k][1] = nums[j];array[k][2] = nums[n];array[k++][3] = nums[m];while (n < m && nums[n] == nums[n+1]) n++;while (n < m && nums[m] == nums[m-1]) m--;n++;m--;}}}}*returnSize = k;*returnColumnSizes = (int *)malloc(sizeof(int) * k);for (int i = 0; i < k; i++) {(*returnColumnSizes)[i] = 4;}return array;
}