代码随想录第七天刷题

第一题为：四数相加II

分为四步

1. 拆成两组
2. 第一组：枚举 + 记哈希表
3. 第二组：枚举 + 查哈希表
4. 累加答案

第一步：

左边组：nums1 + nums2 右边组：nums1 + nums2

目标：left_sum + right_sum == 0 或者 left_sum ==-right_sum

第二步：

【第一组：枚举 nums1 + nums2】

用 hashmap 记录：key = n1 + n2, value = 出现次数

for n1 in nums1:

for n2 in nums2:

hashmap[n1 + n2] += 1

例子：

nums1 = [1, 2]

nums2 = [-1, -2]

得到：

0 → 出现 2 次

-1 → 出现 1 次

1 → 出现 1 次

第三步：

【第二组：枚举 nums3 + nums4】

对每个 n3 + n4，计算 key = -(n3 + n4)

去 hashmap 查这个 key 的次数，累加到 count

for n3 in nums3:

for n4 in nums4:

key = -n3 - n4

if key in hashmap:

count += hashmap[key]

例子：

nums3 = [-1, -2]

nums4 = [1, 2]

(-1)+1=0 → key=0 → hashmap[0]=2 → count+=2

(-1)+2=1 → key=-1 → hashmap[-1]=1 → count+=1

(-2)+1=-1 → key=1 → hashmap[1]=1 → count+=1

(-2)+2=0 → key=0 → hashmap[0]=2 → count+=2

第四步：

count = 2 + 1 + 1 + 2 = 6

return count