代码随想录一刷——454.四数相加II
我们现在前2个数组中，统计元素之和以及出现的次数（用map），随后再另外2个数组中遍历看上面元素之和的相反数是否存在于map中即可。
C++：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
int count = 0;
unordered_map<int,int> umap;
for(int a:nums1)
{
for(int b:nums2)
{
umap[a+b]++;
}
}
for(int c:nums3)
{
for(int d:nums4)
{
int target = 0 - (c+d);
if(umap.find(target)!=umap.end())
count+=umap[target];
}
}
return count;
}
};
Python:
字典
class Solution(object):
def fourSumCount(self, nums1, nums2, nums3, nums4):
"""
:type nums1: List[int]
:type nums2: List[int]
:type nums3: List[int]
:type nums4: List[int]
:rtype: int
"""
"""
hashmap = dict()
count = 0
for n1 in nums1:
for n2 in nums2:
hashmap[n1+n2] = hashmap.get(n1+n2,0)+1
for n3 in nums3:
for n4 in nums4:
key = -n3 -n4
if key in hashmap:
count += hashmap[key]
return count
"""
from collections import defaultdict
result,cnt = defaultdict(lambda:0),0
for n1 in nums1:
for n2 in nums2:
result[n1+n2] +=1
for n3 in nums3:
for n4 in nums4:
cnt += result.get(-n3-n4,0)
return cnt
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];
int sum = 0;
int target = 0;
int cnt = 0;
for(int i = 0;i < HASH_SIZE;i++)
{
hashmap[i] = malloc(sizeof(node));
hashmap[i]->next = NULL;
}
for(int i=0;i<nums1Size;i++)
{
for(int j=0;j<nums2Size;j++)
{
sum = nums1[i]+nums2[j];
hash_insert(hashmap,sum);
}
}
for(int i=0;i<nums3Size;i++)
{
for(int j = 0;j<nums4Size;j++)
{
target = -nums3[i]-nums4[j];
cnt += hash_search(hashmap,target);
}
}
return cnt;
}