训练营day7|三数之和,四数之和
赎金信和四数相加和昨天的差不多。遍历的时候记录一些数据到哈希表里。
三数之和和四数之和可以抽象为双指针找两数之和(不是 two sum,这里的两数之和不用找索引,只用找值)
两数之和主要是有一个去重的操作,即找到第一个和前面不重复的数字。然后继续在剩下的数组里面找是和为target的两个数字。
def move2NextDiff(i,nums): i=i+1 while i<len(nums): if nums[i]==nums[i-1]: i+=1 else: return i return None
while k and l and k<l: if nums[i]+nums[k]+nums[l]+nums[j]<target: k+=1 elif nums[i]+nums[k]+nums[l]+nums[j]>target: l-=1 else: res.append([nums[x] for x in [i,j,k,l]]) k = move2NextDiff(k,nums)