************
思路
一、暴力，四重循环，时间复杂度 O(n⁴)（我没试）
二、（我愿称之）时间复杂度拆分法，将四个嵌套循环拆成两个双层嵌套循环，这样时间复杂度降低至O(n ²)。
将前两个数组的所有和存储在map中，key值记录两数和，val记录出现次数，之后再用嵌套循环计算后两数和，查找map中是否出现过需要的另外两数之和
代码 时间复杂度拆分法（map实现）
typedef struct map {
int key;
int val;
struct map* next;
} mapnode;
#define MapSize 100
mapnode* Map[MapSize];
// 哈希函数
int hash(int key) { return (key % MapSize + MapSize) % MapSize; }
// 创建新的map节点
mapnode* create(int key) {
mapnode* pair = (mapnode*)malloc(sizeof(mapnode));
pair->key = key;
pair->val = 1;
pair->next = NULL;
return pair;
}
// 将新的和添加到map
void Mapadd(int key) {
int index = hash(key);
mapnode* p = Map[index];
mapnode* aim = NULL;
while (p != NULL) // 查看是否已经记录过当前key
{
if (p->key == key) {
p->val++;
aim = p;
break;
}
p = p->next;
}
if (aim == NULL) // 若没有记录过,创建新的
{
aim = create(key);
aim->next = Map[index];
Map[index] = aim;
}
return;
}
int search(int key) {
int index = hash(key);
mapnode* p = Map[index];
while (p != NULL) {
if (p->key == key) {
return p->val;
}
p = p->next;
}
return 0;
}
void destory(void) {
for (int i = 0; i < MapSize; i++) {
if (Map[i] != NULL) {
mapnode* pair = Map[i];
while (pair != NULL) {
mapnode* temp = pair;
pair = pair->next;
free(temp);
}
}
}
return;
}
int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size,
int* nums3, int nums3Size, int* nums4, int nums4Size) {
memset(Map, 0, sizeof(Map));
for (int i = 0; i < nums1Size; i++) {
for (int j = 0; j < nums2Size; j++) {
Mapadd(nums1[i] + nums2[j]);
}
}
int sum = 0;
for (int i = 0; i < nums3Size; i++) {
for (int j = 0; j < nums4Size; j++) {
int key = 0 - nums4[j] - nums3[i];
sum += search(key);
}
}
destory();
return sum;
}
********
思路
哈希表记录 数组magazine中出现过的字母的次数（遍历），再用 数组ransomNote中出现过的字母减去记录好的次数（再遍历），出现负数代表不能，返回false结束，若顺利遍历结束，返回true。
代码
bool canConstruct(char* ransomNote, char* magazine) {
int a[30] = {0};
for (int i = 0; i < strlen(magazine); i++) {
a[magazine[i] % 26]++;
}
for (int i = 0; i < strlen(ransomNote); i++) {
if (a[ransomNote[i] % 26] == 0) {
return false;
} else {
a[ransomNote[i] % 26]--;
}
}
return true;
}
********
难点
1、二维数组malloc易出错，初始化易出错
2、去重思维不好把握，细节太多
思路
双指针，先排序，for循环遍历每个元素，固定a（注意去重，判断当前元素与前一项是否相等），用两个指针left（去重）和right（去重）循环a右边元素，根据三数大小进行对left和right的调整
left和right的去重是在找到符合题目要求的元素之后进行，避免越过答案。
代码
#define MaxSize 20000
int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); }
int** threeSum(int* nums, int numsSize, int* returnSize,
int** returnColumnSizes) {
qsort(nums, numsSize, sizeof(int), cmp);
int** a = (int**)malloc(sizeof(int*) * MaxSize);
for (int i = 0; i < MaxSize; i++) {
a[i] = (int*)malloc(sizeof(int) * 3);
}
int left, right;
*returnSize = 0;
for (int i = 0; i < numsSize - 2; i++) {
if ((i != 0 && nums[i] == nums[i - 1]) || nums[i] > 0)
continue;
left = i + 1;
right = numsSize - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
a[*returnSize][0] = nums[i];
a[*returnSize][1] = nums[left];
a[*returnSize][2] = nums[right];
(*returnSize)++;
while (left < numsSize - 1 && nums[left] == nums[left + 1]) {
left++;
}
while (right > i + 1 && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else {
left++;
}
}
}
*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < (*returnSize); i++) {
(*returnColumnSizes)[i] = 3;
}
return a;
}
********
思路
写过三数之和之后，这题是几乎一样的
易错点
1、left和right去重，while循环之后还要进行一步left++和right--，不然很可能编译不通过
2、i和j剪枝时注意不要单纯判断nums[i]>target,当target是负数时，很容易错过正确答案
代码
#define MaxSize 2000
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** a = (int**)malloc(sizeof(int*) * MaxSize);
for (int i = 0; i < MaxSize; i++)
a[i] = (int*)malloc(sizeof(int) * 4);
int left, right;
*returnSize = 0;
qsort(nums, numsSize, sizeof(int), cmp);
for (int i = 0; i < numsSize - 3; i++) {
if (nums[i] > target&&target>0)
break;
if (i != 0 && nums[i - 1] == nums[i])
continue;
for (int j = i + 1; j < numsSize - 2; j++) {
if (nums[i] + nums[j] > target&&target>0)
break;
if (j != i + 1 && nums[j] == nums[j - 1])
continue;
left = j + 1;
right = numsSize - 1;
while (left < right) {
long long sum =
(long long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
a[*returnSize][0] = nums[i];
a[*returnSize][1] = nums[j];
a[*returnSize][2] = nums[left];
a[*returnSize][3] = nums[right];
(*returnSize)++;
while (left + 1 < numsSize && nums[left] == nums[left + 1])
left++;
while (right - 1 > j && nums[right] == nums[right - 1])
right--;
left++;
right--;
} else if (sum > target) {
right--;
} else if (sum < target) {
left++;
}
}
}
}
*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < (*returnSize); i++) {
(*returnColumnSizes)[i] = 4;
}
return a;
}
哈希表总结
头脑风暴：简单数组哈希，链表哈希（处理哈希冲突），哈希函数（处理负数方面），map（哈希进阶版，注意确认key和val的意义），哈希不了（去重要求）就双指针，哈希次数太多（例如四数相加）换思路拆分为两个两个，注意去重操作（分别i，j，left，right都有一些细节）
京公网安备 11010502036488号