3Sum With Multiplicity此題我認為難度並不高，但如果一開始就走入誤區很有可能會非常的難寫到後續，最終在修正幾次過後我有成功的寫出來了，只是程式碼有點醜，還是會帶大家細部的去看這題需要什麼樣的解題思路！
3Sum With Multiplicity 題目詳解
3Sum With Multiplicity 一樣英翻中的話，就是需要計算一個陣列裡面挑出三個位置i,j,k相加的話，數字會等於target的排列組合總共有幾種，我覺得這次的題目比較直觀，可以看上圖的範例更了解題目想表達的意思，我認為這個題目能夠從兩個角度出發
1.一個是先找位置，也就是利用for迴圈將所有可能的位置找出來
2.一個是先找數字，找出有哪些數字能組成target最後再開始找他們可能的組合有多少
而前一個可能性我認為比較簡單，所以我就先嘗試了，但是如果是厲害的同學就會知道這樣的方式雖然程式碼最小，也最簡單，但實際繳交時就會遇到一個狀況
你的running time 太長了！！！ 規定裡面的迴圈長度最高可以達到三千，也就是說跑起來最久能跑到3000的三次方，這樣以效率來講太差了，所以leetcode不會肯定你的答案，那也就是說我們只能夠去朝第二個思路，先找數字來找到可能的排列組合，而當我們找到數字之後，我們就會需要紀錄這個數字重複幾次，並且呢還會有萬一組合是有兩個以上的重複數字組合而成的該怎麼解決，那我們一步一步來，
1.首先因為要找可能的排列組合的話，我們就不會希望陣列有重複數字，否則會造成很多處理上的困難，而使用set這個函數能夠解決我們的問題
new_arr =set(arr)
new_arr = sorted(new_arr)
arr_list = list(new_arr)
2.而在set之前我們會希望能夠將所有的數字重複幾次也先記下來，這樣才能夠方便我們找出排列組合之後回來查找，我在第一次寫的時候是使用字典的方式紀錄，但事後去做research發現有一個python內建的資料結構叫做collections裡面呢使用counter()就可以將重複的數組做計算，那總之我們先建立一個存放數字重複幾次的表
new_arr = sorted(arr)
for y in range(0,101):
for x in new_arr:
if x==y:
new_dict.setdefault(x,new_arr.count(x)) #存放每個index重複的次數
3.再來呢我們就是針對set好的表開始做for迴圈，去確認使用者輸入的值加起來能夠等於target，那我們確認的方式有幾種，一種是三者相加等於target，可是這樣就必須要做三迴圈，盡量減少跑起來的時間會是我們寫程式時的一大重點，而第二種則是將target-兩者相加，只要減出來的數字存在於表中，就代表這個組合是存在的。
for i in range(longA):
for j in range(i, longA):
k = target - arr_list[i] - arr_list[j]
if k >= arr_list[j] and k in new_arr:
4.在找到組合之後，我們並不能馬上去存放數字重複幾次的表拿數字，因為實際狀況跟想像的有出入的是，萬一找到的三個字裡面有重複的話，我們這樣運算就會是錯的，我們必須要去確認重複幾個數字之後，做簡單的處理，譬如如果重複兩個數字的話，得到的組合應該會是將重複數字在表裡面有幾個做Ｃ4取2的排列組合，最後在乘沒有重複的值，這樣才會是答案，而如果是重複三個的話，則會是C6取3的排列組合去乘總共的數值
if arr_list[i] != arr_list[j] != k: # i!=j!=k
count = count + new_dict[arr_list[i]]*new_dict[arr_list[j]]*new_dict[k]
print(new_dict[arr_list[i]]*new_dict[arr_list[j]]*new_dict[k])
elif arr_list[i] == arr_list[j] and arr_list[j] != k: #前兩者一樣
count = count + (new_dict[arr_list[i]]*(new_dict[arr_list[i]]-1)/2)*new_dict[k]
print((new_dict[arr_list[i]]*(new_dict[arr_list[i]]-1)/2)*new_dict[k])
elif arr_list[j] == k and arr_list[i] != arr_list[j]: #後兩者一樣
count = count + (new_dict[arr_list[j]]*(new_dict[arr_list[j]]-1)/2)*new_dict[arr_list[i]]
else:
count = count + (new_dict[k]*(new_dict[k]-1)*(new_dict[k]-2))/6
大家可以看到最後一段有一點亂，這邊就是我處理資料的型態其實做的不是很好，導致在處理上會有很多問題，所以還是推薦大家使用collections.counter的方式而非用字典來紀錄值重複了幾次，那最後值得注意的一點是，題目有提示你怕回傳的數值太大，必須要使用10^9+7 modulo，如果沒看過這個的同學，這邊簡單的講解就是，害怕回傳數字太大超過程式可以讀取的範圍，所以將數字去％10^9+7，就可以將數字減少，並且利用這個通用的方式在之後要取真正的數字之後，回乘即可，那下面就放完整的程式碼，讓大家參考（抄？），今天的講解就到這裡！
class Solution:
def threeSumMulti(self, arr: List[int], target: int) -> int:
#要先能挑出三者加起來等於target的index
if len(set(arr)) == 1: #此處為避免重複數字的值導致大量浪費運算時間
long = len(arr)
count2 = (long*(long-1)*(long-2))/6
if count2>1000000007: #取模並免數字溢出
count2 = count2 % 1000000007
return int(count2)
new_dict = {}
count = 0
new_arr = sorted(arr)
for y in range(0,101):
for x in new_arr:
if x==y:
new_dict.setdefault(x,new_arr.count(x)) #存放每個index重複的次數
new_arr =set(arr)
new_arr = sorted(new_arr)
arr_list = list(new_arr)
print("新的表",arr_list)
print("存放重複值",new_dict)
longA = len(arr_list)
#開始判斷
for i in range(longA):
for j in range(i, longA):
k = target - arr_list[i] - arr_list[j]
if k >= arr_list[j] and k in new_arr:
print(arr_list[i],arr_list[j],k)
if arr_list[i] != arr_list[j] != k: # i!=j!=k
count = count + new_dict[arr_list[i]]*new_dict[arr_list[j]]*new_dict[k]
print(new_dict[arr_list[i]]*new_dict[arr_list[j]]*new_dict[k])
elif arr_list[i] == arr_list[j] and arr_list[j] != k: #前兩者一樣
count = count + (new_dict[arr_list[i]]*(new_dict[arr_list[i]]-1)/2)*new_dict[k]
print((new_dict[arr_list[i]]*(new_dict[arr_list[i]]-1)/2)*new_dict[k])
elif arr_list[j] == k and arr_list[i] != arr_list[j]: #後兩者一樣
count = count + (new_dict[arr_list[j]]*(new_dict[arr_list[j]]-1)/2)*new_dict[arr_list[i]]
else:
count = count + (new_dict[k]*(new_dict[k]-1)*(new_dict[k]-2))/6
print(int(count)%1000000007)
return(int(count)%1000000007)