作者：feintKotlin

題目來源：hackerrank

關鍵字：算法；kotlin；流程圖；程序；

算法挑戰第十一天，難度中等

題目

Watson給了Sherlock一個數組A1,A2...AN。 然後，他問Sherlock能否找到數組中的一個元素滿足，數組中該元素的左邊元素之和與該元素右邊元素 之和相等。如果該元素左邊（或者右邊）沒有元素，對應的和視為0。說正式點，就是找到 i, 滿足： A1+A2...A{i-1} = A{i+1}+A{i+2}...AN。

輸入格式

第一行包含一個整數 T, 測試數據的組數。每組測試數據第一行包含N, 數組A中的元素個數。每組數據的第二行包含N個空白分隔的整數，表示數組 A中的元素。

輸出格式

對每組測試數據, 如果有數組中這樣的元素，滿足數組中該元素的左邊元素之和與該元素右邊元素之和相等，輸出YES， 否則，輸出NO。

約束條件

• 1 ≤ T ≤ 10

• 1 ≤ N ≤ 10^5

• 1 ≤ A_i ≤ 2*10^4，對所有1 ≤ i ≤ N

實例輸入

2

3

1 2 3

4

1 2 3 3

實例輸出

NO

YES

實例分析

第一組測試數據, 沒有這樣的元素下標。 第二組測試數據, A[1]+A[2] = A[4], 因此存在滿足條件的下標3。

(以上為題目的相關內容，大家可以先自己思考一翻，然後在瀏覽下方的解題過程)

解析

這道題的難度不大，邏輯也比較簡單。為了不重複的進行累加操作，我使用了兩個變量來分別保存當前元素左右兩側元素的和的值。這樣每次移動下標時左右兩側分別自要進行一次加操作（左邊）和一次減法操作（右邊）。在這裡我設定下標的初始位置為0（最左邊），當然如果是從中間開始的話有更大的概率能使用更少的操作得到最後的結果。不過現在都已經是O(n)的時間複雜度了，那樣做的意義不大，還會增加算法的複雜度，咱就沒有考慮使用那種方式了。

流程圖

流程圖

代碼

代碼

---

結語：真煩惱，昨晚選的一道動態規劃的題目，似乎難度選高了，想了一個多小時還是沒什麼頭緒。。。哎今早先來道Search類的題目（這道題挺貼心的，還自帶中文翻譯，省了我不少事，）熱熱身，或許就來靈感了呢 —_- 。