Problem#
給你正整數 $n$ 要你找到 pivot $i$ 使得 $1+2+\cdots +i = i + (i+1) + (i+2) + \cdots + n$,如果找不到則回傳 -1
測資限制#
- $1 \le n \le 1000$
想法#
前綴和(Prefix Sum) 預處理 $O(n)$,查詢 $O(1)$ 可以算出 $[a, b]$ 之間相加,枚舉 $[1, n]$ 當 pivot 去看相加有沒有相等即可
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$