代码随想录算法训练营第六天 - 哈希表part02

454.四数之和II

核心思想：利用字典的key，value
4个数组两两分组，nums1+nums2 的两两元素之和 及 计数 先存入字典中，然后对nums3和nums4的进行元素相加 然后对比字典中是否有对应的key，有就count+value

class Solution(object):def fourSumCount(self, nums1, nums2, nums3, nums4):n=len(nums1)hashmap=dict()count=0for n1 in nums1:for n2 in nums2:if (n1+n2) in hashmap:hashmap[n1+n2]+=1else:hashmap[n1+n2]=1for n3 in nums3:for n4 in nums4:k=-(n3+n4)if k in hashmap:count+=hashmap[k]return count

15. 三数之和

重点是去重的逻辑，对a,b,c分别设计去重逻辑，妙（是说卡哥

        nums.sort()n=len(nums)res=[]for i in range(n):left=i+1right=n-1#a去重，因为nums[i]值不变,后面nums[left],nums[right]的组合就会有可能重复，直接跳过#但需要i>0,和前一个元素做对比。 如果是对比num[i] num[i+1],会错过b值if i>0 and nums[i]==nums[i-1] :continuewhile left<right:if(nums[i]+nums[left]+nums[right]>0):right-=1elif(nums[i]+nums[left]+nums[right]<0):left+=1else:res.append([nums[i], nums[left], nums[right]])#当遇到nums[i],nums[left]固定，right指向的值和前一个相等，则可以跳过while left<right and nums[right]==nums[right-1]:right-=1while left<right and nums[left]==nums[left+1]:left+=1right-=1left+=1return res

18.四数之和

…待写