ProblemM Managing Difficulties (Complex Optimization)

題目大意：

給你一斷數列
判斷裡面的值有幾個是可以符合公式 \(a_j−a_i=a_k−a_j\)

分析：

這題很簡單，就是要著重在效率時顯得十分棘手。
我將分成 3 個部分說明。

1. 透過字典優化
   可將公式移項成 \(2a_j = a_i + a_k \)，加上 i > j > k
   透過字典的部分能夠將 \(a_k\) 點就可以省略掉 for k 的迴圈

2. j 從最後 n - 1 開始往前 for
   如果只透過 1. 會發現一個問題，因為在每次 i 結束時，需要再將之前刪除的 dict[j] 值補回，會增加一個 for與是透過反向輸出，可省略掉須將刪除的 dict[j] 補回，於是減少一個 for了!

3. 使用unorder_map
   map 會造成效率增加 \( o (n \log \ n)\)，少量使用內存。
   unordered_map 則是效率減少 \(o(1)\)，大量使用內存。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int num[2020] = {} ;


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t , n , ans, now  ;
    cin >> t ;
    while(t--){
        cin >> n ;
        unordered_map<int ,int > dict ;
        ans = 0 ;
        for(int i = 0 ; i < n ; i++){
            cin >> num[i] ;
        }

        dict[num[n-1]] += 1 ;
        for(int j = n-2 ; j > 0 ; j--){
            for(int i = 0 ; i < j ; i++ ){
                now = 2 * num[j] - num[i] ;
                ans += dict[now];
            }
            dict[num[j]]+=1 ;
        }
        cout << ans << '\n' ;
    }

    return 0;
}