724. Find Pivot Index

harry xie
2024-10-01 07:37:01

解題程式碼

var pivotIndex = function (nums) {
  let sum = nums.reduce((tol, acc) => (tol += acc), 0);
  let leftSum = 0;

  for (let i = 0; i < nums.length; i++) {
    let rightSum = sum - leftSum - nums[i];
    if (leftSum === rightSum) return i;
    leftSum += nums[i];
  }
  return -1;
};

解題思路演算法

這題可以這樣想，假設 nums 是 [1,7,3,6,5,6]，那整個陣列的元素值加起來是 28，而 Pivot Index 可看出是在 index = 3 的位置

前面的 left sum(1 + 7 + 3) = 11，right sum(5 + 6) = 11，所以可以推導出 right sum 就是 28 - left sum - Pivot Index 的元素值

可參考這篇文章的圖片:

724. 寻找数组的中心下标（前缀和，清晰图解）

解法的時間空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

Find Pivot Index - Leetcode 724 - Python

Prefix Sums（前綴和）概念