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+10
bool 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 100
int 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;
}
注意边界判断于整型溢出