Equal Sides Of An Array

Posted on | In

題目

You are going to be given an array of integers(arr). Your job is to take that array and find an index N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no index that would make this happen, return -1.

Input: An integer array of length 0 < arr < 1000. The numbers in the array can be any integer positive or negative.

Output: The lowest index N where the side to the left of N is equal to the side to the right of N. If you do not find an index that fits these rules, then you will return -1.

Note: If you are given an array with multiple answers, return the lowest correct index.
An empty array should be treated like a 0 in this problem. (Link)

思路

為了避免重複計算，我想利用兩個變數，一個儲存某index前的總和，一個則是所有的總和。接著利用迴圈，看跑到哪個index，此index前的總和會等於他後面的總和(全部-前面)。

Pseudocode

1
2
3
4
5
6
前面的總和 = 0
for i in arr：
  if前面的總和 = 所有總和 - 前面的總和
    return 此index
  若沒有，則前面的總和加上此項數字，繼續下一個迴圈
若跑完都沒有符合，return -1

Code

1
2
3
4
5
6
7
8
9
10
def find_even_index(arr):
    temp = 0
    total = 0
    for i in arr:
        total += i

    for i in range(len(arr)):
        if temp == total - temp - arr[i]: return i
        temp += arr[i]
    return -1               # Runtime: 161 ms

分析

先利用一個迴圈算出total，再利用第二個迴圈依序跑index，看看到哪一項會符合前總和等於後總和。

此演算法的運作時間：

  • 兩次for-loop皆為O(n)

整體Time complexity 為 O(n)

參考他人作法

1
2
3
4
5
def find_even_index(arr):
    for i in range(len(arr)):
        if sum(arr[:i]) == sum(arr[i+1:]):
            return i
    return -1              # Runtime: 176 ms

分析

整體概念是一樣的，只是利用了sum()方法來加總List內的項目。但sum()其實會瀏覽整個list，所以他運作的時間是O(n)，而此方法將sum()擺在for-loop內不斷重複運算，整體的Time complexity是O(n2)的。在此例因為輸入的arr數量並不大，所以在運作時間上差異並不顯著，但當data龐大起來，這個方法的效率會比我寫的方法慢上許多。

另外，在另一個人的解法當中提到，為了方便管理，其實一個函數不適合多個return。所以在我的方法中，若是能將return i及return -1改掉，先把i和-1 assign給一個變數result，最後只需寫一次return result即可。