代碼隨想錄

思路：首先用雙循環遍歷構成a+b的值和出現的次數，用字典接收，由于a+b+c+d=0，因為在對c和d進行雙循環后，在字典中找到0-c-d，得出它的值也就是出現次數，進行出現次數的累計，就得到了

有多少個元組?(i, j, k, l)?能滿足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0? ? ? ? ? ? ? ? ? ? ?

  class Solution:def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:hashmap =dict()for a in nums1:for b in nums2:hashmap[a+b]=hashmap.get(a+b,0)+1 count = 0for c in nums3:for d in nums4:target = -c-dif target in hashmap:count+=hashmap[target]return count

  題目二：贖金信?

• 題目鏈接/文章講解： 代碼隨想錄

  思路：通過比較贖金信的各個字母出現的次數都要小于等于雜志出現的字母個數來判定，定義數組，用26個字母的unicode次序來確定索引，每個字母出現一次，對應索引次數加1

  class Solution:def canConstruct(self, ransomNote: str, magazine: str) -> bool:ransomNote_count = [0]*26magazine_count = [0]*26for i in ransomNote:ransomNote_count[ord(i)-ord('a')]+=1for i in magazine:magazine_count[ord(i)-ord('a')]+=1return all(ransomNote_count[a]<=magazine_count[a] for a in range(26))

  題目三：三數之和

  思路：

  使用雙指針的方法，每遍歷一次數組，都是先讓左邊第一個數作為i，固定，讓left往右移動，right往左移動進行遍歷，如果sum>0,則讓right往左移動，如果sum<0，則讓left往右移動；注意點是i和left以及right的去重，

  i的去重：檢查第i項以及第i-1項是否相等，如果相等，就跳過

  left 和right的去重：等到往結果result中加入一個元組之后，在考慮去重，只要當前right和往左移動后的下一個right數組對應的值相等，就right減一，left同理

  class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:result = []nums.sort()for i in range(len(nums)):if nums[i]>0:return resultif i>0 and nums[i]==nums[i-1]:continueleft = i+1right = len(nums)-1while left < right:sum_ = nums[i]+nums[left]+nums[right] if sum_ >0:right -=1elif sum_ <0:left +=1else:result.append([nums[i],nums[left],nums[right]])while left < right and nums[right] == nums[right-1]:right -=1while left < right and nums[left] == nums[left+1]:left +=1right-=1left +=1return result

  題目四：四數之和

  思路：跟三數之和，相比，一是多了一層循環，多了一次去重；二是由于target不確定是否是大于零還是小于零，因此需要進行一級剪枝操作，也就是如果nums[k]大于零,且target大于零，且nums[k]>0，那么就跳出循環；二級剪枝操作，判斷nums[k]+nums[i]>target 且target大于零，是的話就跳出循環

  class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:result =[]nums.sort()n = len(nums)for k in range(n):if(nums[k]>target and target >0 and nums[k]>0):breakif(k>0 and nums[k]==nums[k-1]):continuefor i in range(k+1,n):if(nums[k]+nums[i]>target and target >0):breakif(i>k+1 and nums[i]==nums[i-1]):continueleft  = i+1right = n-1while left < right:sum_ = nums[k]+nums[i]+nums[left]+nums[right]if sum_ > target:right -=1elif sum_ < target:left +=1else:result.append([nums[k],nums[i],nums[left],nums[right]])while left < right and nums[left] == nums[left +1]:left +=1while left < right and nums[right] == nums[right-1]:right -=1left +=1right -=1return result