[LeetCode] #454. 4Sum II
題目
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
直覺解
構想一（失敗）：
用 for 回圈把所有組合都嘗試一次
python 3 實作：
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
count = 0
for i in nums1:
for j in nums2:
for k in nums3:
for l in nums4:
if i +j + k + l == 0:
count += 1
return count
錯誤：Time Limit Exceeded
input:
nums1 = [-8,-7,-14,-5,5,-24,-16,-24,-23,6,3,-26,-10,-14,-22,-11,-30,-2,-15,-18,-31,-1,-16,-22,-23,-24,-22,-16,-24,-15,-21,-18,-8,-7,7,-20,-32,-16,-24,5,3,-31,-18,2,-2,-11,-21,-26,-15,-14,1,10,0,-2,2,-10,3,-12,-10,-30,8,-31,2,-2,-4,-17,-24,-25,6,-11,-4,-29,5,-20,-16,-23,2,-27,6,-10,-2,-29,-15,9,-13,-20,8,-2,-17,6,-5,-26,6,-9,-29,-32,-27,-20,-7,-28]
nums2 = [-9,-6,-6,-24,-4,-25,0,-17,1,-10,-18,4,1,8,-28,3,8,4,-18,-18,-10,0,1,-23,-10,-8,-18,-13,-30,-8,-24,1,-24,5,-15,-19,-6,-7,2,-10,-24,-9,-15,-2,-28,-3,-24,7,-22,-9,-18,-4,-5,-28,-5,-22,-31,-2,0,-20,-9,-14,-32,-12,8,-22,-15,4,-9,-26,2,-5,-20,-13,-12,-13,-20,-8,-32,6,-4,-29,-5,4,-21,-13,-26,5,6,-25,-31,-15,10,3,5,5,-10,1,-7,8]
nums3 = [-6,6,-14,0,-2,-7,-16,0,-25,-28,0,0,-18,-15,4,-7,-26,-21,-3,-5,9,-14,6,-5,-26,-25,-27,-1,10,-13,7,-2,1,6,-12,7,-24,9,5,-27,8,-3,-12,-31,-27,-9,-10,-8,-27,-2,-20,-27,-13,0,8,-1,-25,0,10,-14,-23,-2,5,-28,-22,5,-12,-14,-15,8,-9,-6,-9,-22,-10,-31,-9,-24,-16,-13,-26,-5,-32,-29,9,-3,-10,8,-15,-31,-5,-18,5,-20,-2,10,-18,3,-1,-31]
nums4 = [-5,4,-4,-20,-32,7,-12,-15,-26,-15,6,2,-24,-14,-31,-11,-29,-5,-1,5,-29,-1,-26,-17,-12,-14,-12,6,-28,-28,9,-29,-22,-1,-31,1,-4,-24,-25,-18,8,-21,-29,0,5,-21,-10,-4,-25,-15,-32,-29,-15,-31,-25,6,-30,-23,7,-6,4,-32,9,-11,7,3,-21,-30,-25,-1,-13,-11,-24,-27,-12,-24,-27,-22,-31,-4,-20,-31,7,2,-25,-3,-12,-24,10,10,-9,-17,-22,-1,-16,-11,6,10,-20,5]
構想二（失敗）：
用 dictionary 紀錄 list 中每個數字出現的次數，避免重複的數字被重複計算。
python 3 實作：
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
def counter(list):
count = {}
for i in list:
if not count.get(i, None):
count[i] = 0
count[i] += 1
return count
count = 0
nums1 = counter(nums1)
nums2 = counter(nums2)
nums3 = counter(nums3)
nums4 = counter(nums4)
for i in nums1:
for j in nums2:
for k in nums3:
for l in nums4:
if i + j + k + l == 0:
count += nums1[i] * nums2[j] * nums3[k] * nums4[l]
return count
錯誤：Time Limit Exceeded
input:
nums1 = [-268434543,-268434778,-268435208,-268434948,-268435390,-268435258,-268435289,-268434617,-268435342,-268434922,-268435335,-268434715,-268435400,-268435185,-268434954,-268435137,-268435347,-268435033,-268434503,-268435311,-268435232,-268434779,-268435053,-268434707,-268435036,-268434992,-268434657,-268434765,-268434865,-268435101,-268434896,-268435278,-268434732,-268434645,-268435157,-268435159,-268434992,-268434926,-268435392,-268435189,-268434917,-268434970,-268435118,-268434628,-268434910,-268434900,-268434498,-268435095,-268434590,-268435056,-268434510,-268435262,-268434917,-268434656,-268435001,-268435305,-268434595,-268434997,-268435373,-268434600,-268435166,-268434863,-268434960,-268435299,-268435292,-268434737,-268434749,-268434475,-268435015,-268434942,-268435006,-268434836,-268435068,-268435432,-268434460,-268435135,-268434877,-268435047,-268434545,-268435171,-268434784,-268435301,-268434939,-268434996,-268435000,-268434837,-268435377,-268434755,-268434955,-268435412,-268434724,-268434631,-268435113,-268435296,-268434505,-268435292,-268435071,-268435304,-268435058,-268434562]
nums2 = [-268434750,-268435259,-268434823,-268435095,-268434566,-268435280,-268434753,-268435210,-268434616,-268435294,-268435414,-268434745,-268435196,-268435225,-268434535,-268434746,-268435416,-268435298,-268434836,-268434975,-268434712,-268434720,-268435142,-268435091,-268434568,-268435044,-268435433,-268434915,-268434792,-268434947,-268434969,-268435133,-268434973,-268434997,-268435348,-268435203,-268434692,-268435021,-268434689,-268434677,-268435291,-268434833,-268434577,-268435130,-268435387,-268434650,-268434797,-268435376,-268435244,-268434503,-268435433,-268434729,-268434825,-268434727,-268434738,-268435256,-268435340,-268434750,-268435173,-268435310,-268435078,-268435453,-268435037,-268434638,-268434897,-268434983,-268434865,-268434510,-268435063,-268434512,-268434995,-268435048,-268434788,-268435430,-268434596,-268434515,-268434843,-268435235,-268435041,-268435194,-268435141,-268435150,-268434643,-268435013,-268434590,-268435261,-268435256,-268434799,-268434697,-268434609,-268434861,-268434687,-268434732,-268435031,-268434542,-268434946,-268434542,-268435085,-268435337,-268435233]
nums3 = [268435123,268434786,268434802,268435142,268434477,268434984,268434962,268434956,268435125,268434457,268435295,268435014,268434895,268434895,268435285,268435141,268434822,268434661,268435106,268435446,268435275,268434652,268434600,268435268,268434858,268434701,268435439,268434582,268435099,268434701,268435444,268434576,268435179,268434786,268435213,268435064,268434829,268434559,268434611,268435214,268434857,268435134,268434992,268435418,268434915,268435342,268434626,268434987,268434712,268435005,268434666,268435297,268434665,268435082,268434524,268434798,268434708,268435011,268434978,268435299,268435035,268435026,268435324,268434603,268435230,268435247,268435119,268434660,268435053,268434613,268434766,268434718,268434794,268434714,268434860,268434949,268434597,268434489,268435099,268435148,268434560,268435150,268435360,268434937,268435019,268434867,268435084,268435442,268434483,268435396,268435292,268435325,268434912,268435391,268434483,268435441,268434640,268435034,268435395,268435059]
nums4 = [268435003,268435419,268434638,268434623,268434978,268434780,268435037,268434800,268434864,268435367,268435082,268434465,268435075,268435043,268434858,268434912,268435313,268434636,268434547,268434462,268435015,268434739,268434807,268434485,268434644,268434757,268434758,268435350,268434942,268434586,268434742,268435308,268434612,268435133,268434863,268434563,268434479,268435143,268434568,268434824,268435332,268435406,268434534,268435219,268435423,268435247,268435416,268435032,268435379,268434559,268435245,268435169,268434774,268435153,268435097,268435317,268434875,268435446,268435296,268434991,268434914,268434846,268434600,268434580,268435176,268435324,268434723,268435078,268435117,268435372,268435262,268434924,268435299,268435382,268434541,268435423,268434870,268435318,268435232,268434721,268434469,268435308,268434504,268434819,268434604,268434829,268435356,268435307,268434938,268435171,268435094,268435327,268434603,268434629,268434902,268435272,268434569,268434973,268434690,268435383]
構想三（失敗）：
用 dictionary 紀錄 list 中每個數字出現的次數，避免重複的數字被重複計算。將數字排序，以便儘早脫離不可能的組合。不要用迭代 nums4 的方式找出第四個數，而是用 dictionary 查詢 nums4 中是否有符合的數。
python 3 實作：
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
def counter(list):
count = {}
for i in list:
if not count.get(i, None):
count[i] = 0
count[i] += 1
return count
count = 0
nums1 = counter(nums1)
nums2 = counter(nums2)
nums3 = counter(nums3)
nums4 = counter(nums4)
sorted_nums1 = sorted(nums1.keys())
sorted_nums2 = sorted(nums2.keys())
sorted_nums3 = sorted(nums3.keys())
sorted_nums4 = sorted(nums4.keys())
max_nums2 = sorted_nums2[len(sorted_nums2) - 1]
min_nums2 = sorted_nums2[0]
max_nums3= sorted_nums3[len(sorted_nums3) - 1]
min_nums3 = sorted_nums3[0]
max_nums4 = sorted_nums4[len(sorted_nums4) - 1]
min_nums4 = sorted_nums4[0]
max_sum_nums234 = max_nums2 + max_nums3 + max_nums4
min_sum_nums234 = min_nums2 + min_nums3 + min_nums4
max_sum_nums34 = max_nums3 + max_nums4
min_sum_nums34 = min_nums3 + min_nums4
for i in sorted_nums1:
if i + max_sum_nums234 < 0:
continue
if i + min_sum_nums234 > 0:
continue
for j in sorted_nums2:
if i + j + max_sum_nums34 < 0:
continue
if i + j + min_sum_nums34 > 0:
continue
for k in sorted_nums3:
difference = 0 - i - k - j
if nums4.get(difference):
count += nums1[i] * nums2[j] * nums3[k] * nums4[difference]
return count
過程中犯過的錯誤：把 continue 寫成 break，導致無法迭代 list 中的所有元素
錯誤：Time Limit Exceeded
input:
nums1 = [87,-63,-63,-9,-86,-63,-86,7,63,-36,-58,29,47,-6,-82,49,80,62,-12,-51,-20,68,-22,-90,8,-37,15,-18,66,5,-44,0,89,55,-24,6,74,-43,-18,79,-58,-90,0,50,-61,-53,-25,-26,-53,-59,43,-9,-37,-71,-73,6,75,-56,95,37,56,-100,0,-86,69,5,-56,76,14,-58,-60,-49,-76,-82,-28,-7,65,-88,-29,32,48,-90,41,71,-38,-13,33,-4,-77,34,31,59,73,-6,56,98,8,-51,-6,-70,-90,-46,-84,55,70,-18,-41,-87,6,-37,7,-8,63,-40,72,7,21,-35,37,-74,-27,-76,29,44,-65,75,-57,-33,-87,-3,71,-85,-97,-91,3,3,-74,4,-71,-79,-49,88,-4,14,51,-41,36,-68,22,-71,-56,-58,-88,-9,-8,-86,68,76,-74,-20,-86,-26,46,10]
nums2 = [57,58,-63,34,91,-66,69,-97,89,-88,5,17,-60,69,-32,10,56,77,-18,-100,49,50,85,-43,95,-25,42,31,-41,-33,-56,-54,-55,-18,-93,92,0,59,3,-61,-65,52,-61,-92,-40,-27,64,-50,-89,70,69,-84,-78,78,-27,97,-8,32,66,6,8,6,-12,62,2,-2,55,94,-29,-7,42,-40,42,93,-90,38,100,82,-54,-51,99,-81,73,-66,33,-84,-15,37,26,43,14,-88,21,-65,55,80,-45,38,-77,-91,4,54,-75,-96,-57,-94,18,11,0,17,-71,-72,-50,19,-71,-62,83,-36,42,-20,-65,97,-52,51,53,44,83,-1,-57,48,-69,-15,-8,25,71,17,-95,2,-68,-88,80,-48,65,-12,62,-31,98,45,44,73,46,90,-98,8,-98,-63,73,-25,28,100,-68,52,-40,20]
nums3 = [36,2,-89,-99,-75,-1,52,-42,92,-85,-41,-20,79,-74,-1,-2,54,-13,61,13,-77,-11,-43,-29,21,-17,94,-67,12,95,-20,-54,37,11,4,-39,7,1,-64,-37,-1,38,50,-64,66,73,-71,23,-86,-23,-53,-75,10,33,96,8,2,-48,-51,-45,25,89,81,82,29,75,-23,-84,56,-29,-11,27,-91,-3,-70,-4,-15,-43,27,-20,44,-27,-81,14,-96,-27,-24,-17,18,-32,-17,59,-12,79,-52,-36,-75,-82,91,-67,-42,39,1,-96,-58,42,-24,-42,-30,76,47,86,-56,44,6,-89,-66,-61,-50,24,-56,-93,93,-48,-72,-37,2,81,-22,32,51,-96,12,-22,51,-40,-75,-91,48,-25,-26,-38,99,30,16,76,34,-37,0,55,99,75,34,-97,73,25,9,-13,-1,58,29,-11,32,-85]
nums4 = [75,-87,41,44,69,70,56,-70,87,-62,-5,-91,-65,9,70,-90,-18,-9,5,-76,-58,-90,50,51,-63,84,-39,16,-88,52,-68,-13,24,56,21,31,-100,-16,-17,-48,-17,37,-94,-75,-64,-49,97,-8,-98,15,53,50,-40,27,-13,-25,69,-57,1,41,99,-37,-29,23,100,26,-58,-48,59,-100,-14,-5,44,39,-82,0,-97,-71,21,-55,-19,-12,26,43,37,-83,71,-98,-98,66,99,-69,66,31,16,90,23,-14,69,-76,-47,0,-83,-89,49,77,-25,41,85,37,-17,19,69,34,-83,86,-50,9,95,-32,-40,36,68,-91,-32,56,28,-58,-45,-82,-16,-52,4,3,-13,-34,-39,-73,60,13,34,-55,-97,-28,92,-43,64,-23,-91,35,58,37,46,-57,-40,-16,-65,-36,85,24,-84,31,-15,-1]
參考別人的解
構想四（成功）：
用 dictionary 紀錄 list 中每個數字出現的次數，避免重複的數字被重複計算。將數字排序，以便儘早脫離不可能的組合。把 num3 和 nums4 的組合合併成一個 dictionary，確定好 nums1 和 nums2 的值後，直接在該 dictionary 查詢是否有符合的 nums3 + nums4 的值。
python 3 實作：
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
def counter(list):
count = {}
for i in list:
if not count.get(i, None):
count[i] = 0
count[i] += 1
return count
count = 0
nums1 = counter(nums1)
nums2 = counter(nums2)
nums3 = counter(nums3)
nums4 = counter(nums4)
nums34 = {}
for i in nums3:
for j in nums4:
sum = i + j
if not nums34.get(sum, None):
nums34[sum] = 0
nums34[sum] += nums3[i] * nums4[j]
sorted_nums1 = sorted(nums1.keys())
sorted_nums2 = sorted(nums2.keys())
sorted_nums3 = sorted(nums3.keys())
sorted_nums4 = sorted(nums4.keys())
max_nums2 = sorted_nums2[len(sorted_nums2) - 1]
min_nums2 = sorted_nums2[0]
max_nums3 = sorted_nums3[len(sorted_nums3) - 1]
min_nums3 = sorted_nums3[0]
max_nums4 = sorted_nums4[len(sorted_nums4) - 1]
min_nums4 = sorted_nums4[0]
max_sum_nums234 = max_nums2 + max_nums3 + max_nums4
min_sum_nums234 = min_nums2 + min_nums3 + min_nums4
for i in sorted_nums1:
if i + max_sum_nums234 < 0:
continue
if i + min_sum_nums234 > 0:
continue
for j in sorted_nums2:
difference = 0 - i - j
if nums34.get(difference):
count += nums1[i] * nums2[j] * nums34[difference]
return count
效能：
Runtime: 608 ms, faster than 87.79% of Python3 online submissions for 4Sum II.
Memory Usage: 14.6 MB, less than 20.94% of Python3 online submissions for 4Sum II.
優化構想四（減少使用的空間）：
用 dictionary 紀錄 list 中每個數字出現的次數，避免重複的數字被重複計算。把 num1 和 nums2 、 num3 和 nums4 的組合合併成一個 dictionary。
python 3 實作：
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
def counter(list):
count = {}
for i in list:
if not count.get(i, None):
count[i] = 0
count[i] += 1
return count
def twoSum(dict1, dict2):
result = {}
for i in dict1:
for j in dict2:
sum = i + j
if not result.get(sum):
result[sum] = 0
result[sum] += dict1[i] * dict2[j]
return result
count = 0
nums1 = counter(nums1)
nums2 = counter(nums2)
nums3 = counter(nums3)
nums4 = counter(nums4)
sum_nums1_nums2 = twoSum(nums1, nums2)
sum_nums3_nums4 = twoSum(nums3, nums4)
for i in sum_nums1_nums2:
difference = -i
if sum_nums3_nums4.get(difference):
count += sum_nums1_nums2[i] * sum_nums3_nums4[difference]
return count
效能：
Runtime: 608 ms, faster than 88.02% of Python3 online submissions for 4Sum II.
Memory Usage: 14.4 MB, less than 69.57% of Python3 online submissions for 4Sum II.
Comments
Post a Comment