原始作法 for i in range(n): for j in range(i+1,n): for k in range(j+1,n): for l in range(k+1,n): if A[i]==A[k] and A[j]==A[l]: ans+=1
以下進行最佳化：
1. 如果建一張表，紀錄某個位置之前各個數字出現過幾次，則不用找i。可以把 for i 拆掉, j 改從0+1=1開始： # 建表 # (略) for j in range(1,n): for k in range(j+1,n): for l in range(k+1,n): if A[j]==A[l]: ans+=table[j][A[k]] # 在j之前A[k]這個數字出現過的次數
2. 注意到最低就是j，在j之前的資料不會再被看過。把表壓成1維： for j in range(n): for k in range(j+1,n): for l in range(k+1,n): if A[j]==A[l]: ans+=table[A[k]] table[A[j]]+=1
3. 條件判斷式跟k好像沒甚麼關聯，試著拆 for k 。先把它拿進深層，讓他與有關聯的東西密切一點： for j in range(n): for l in range(j+2,n): if A[j]==A[l]: for k in range(j+1,l): ans+=table[A[k]] table[A[j]]+=1
4. 讓 sum([table[A[k]] for k in range(j+1,l)]) 先算完再放進ans for j in range(n): for l in range(j+2,n): if A[j]==A[l]: ans+=sum([table[A[k]] for k in range(j+1,l)]) table[A[j]]+=1
5. k 那段加太多次 j~後面 的東西了，欠prefixsum for j in range(n): prefixAtJ=[0]*j+[table[A[j]]] for jj in range(j+1,n): prefixAtJ[jj]=prefixAtJ[jj-1]+table[A[jj]] for l in range(j+2,n): s+=table[A[l-1]] if A[j]==A[l]: ans+=prefixAtJ[l-1]-prefixAtJ[j] table[A[j]]+=1
6. 迴圈跑兩次不累嗎，更何況不一定會發生 A[j]==A[l] ，壓平 for j in range(n): s=0 for l in range(j+2,n): s+=table[A[l-1]] if A[j]==A[l]: ans+=s table[A[j]]+=1
LINE