LeetCode 75 Level 1 - Day 1 Prefix Sum

724. Find Pivot Index題目

• 題目連結
• 難易度：Easy

題目敘述

Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.

預設函數

int pivotIndex(int* nums, int numsSize){

}

題目輸入限制

解題過程及程式碼

本題是 Day 1 Prefix Sum 中的第二題，如圖Fig. 1所示，要在輸入陣列裡找到第[i]項(index = 0, 1, 2...i)並回傳index值，以這個index為中心位於左邊項目的和要等於位於右邊項目的和

• 一開始想到的方法是用多個迴圈分別計算和：
  • 先確認輸入陣列除了頭一項的和是不是零，若是則回傳index = 0。
  • 再來假設pivot index = i時，分別迴圈計算[i]左邊的和及[i]右邊總和，若相等則回傳index = i，若找不到則回傳-1。
  • 程式碼上傳：

  int pivotIndex(int* nums, int numsSize){
      int i, j, k;
      int sum_0 = 0;
      int sum_left, sum_right = 0;
  
      /* 確認index = 0情況 */
      for (i=1; i<numsSize; i++) {
          sum_0 += nums[i];
      }
      if (sum_0 == 0) {
          return 0;
      }
  
      /* 確認index > 0情況 */
      for (i=1; i<numsSize; i++) {
          sum_left = 0;
          sum_right = 0;
          for (j=0; j<i; j++) {
              sum_left += nums[j];
          }
  
          for (k=i+1; k<numsSize; k++) {
              sum_right += nums[k];
          }
  
          if (sum_left == sum_right) {
              return i;
          }
      }
      return -1;
  }
  

• 後來發現既然一開始已經將總和計算過了，接下來所有需計算[i]的左邊總和及右邊總和，都和總和相差1個元素而已：
  • 修改後計算時間從1583 ms左右降到31 ms左右
  • 程式碼上傳：

  int pivotIndex(int* nums, int numsSize){
      int i;
      int sum_total = 0;
      int sum_left, sum_right = 0;
  
      /* 確認index = 0情況 -> 計算總和 */
      for (i=0; i<numsSize; i++) {
          sum_total += nums[i];
      }
      if ((sum_total - nums[0]) == 0) {
          return 0;
      }
  
      /* 確認index > 0情況 */
      for (i=1; i<numsSize; i++) {
          sum_left += nums[i-1];
          sum_right = sum_total -  nums[i] - sum_left;  /* 用總和扣掉元素即可 */
  
          if (sum_left == sum_right) {
              return i;
          }
      }    
      return -1;
  }
  

第二天到這裡結束，謝謝大家。