給定一個整數(shù)類型的數(shù)組 nums，請編寫一個能夠返回數(shù)組“中心索引”的方法。

我們是這樣定義數(shù)組中心索引的：數(shù)組中心索引的左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。

如果數(shù)組不存在中心索引，那么我們應(yīng)該返回 -1。如果數(shù)組有多個中心索引，那么我們應(yīng)該返回最靠近左邊的那一個。

示例 1:

輸入:
nums = [1, 7, 3, 6, 5, 6]
輸出: 3
解釋:
索引3 (nums[3] = 6) 的左側(cè)數(shù)之和(1 + 7 + 3 = 11)，與右側(cè)數(shù)之和(5 + 6 = 11)相等。
同時, 3 也是第一個符合要求的中心索引。

示例 2:

輸入:
nums = [1, 2, 3]
輸出: -1
解釋:
數(shù)組中不存在滿足此條件的中心索引。

說明:nums 的長度范圍為 [0, 10000]。任何一個 nums[i] 將會是一個范圍在 [-1000, 1000]的整數(shù)。

我們先分析，先說說我的實現(xiàn)思路，再來分享其他用戶優(yōu)質(zhì)解答。

題目想傳達的意思其實很明確了，當遍歷到 i 時， i 左邊所有元素（不包括i）的和與 i 右邊所有元素（不包括i）的和相等，如果遍歷過程中滿足則返回 i，如果不滿足則返回 -1。

我第一想到的就是每次遍歷 i ,將數(shù)組左右分別拆分成兩個數(shù)組，求和做比較，如果滿足則返回 i ,如果未找到返回 -1；

事先提示這道題的坑，按照我的理解，比如一個數(shù)組[1,-1,1]，其實只用比較i為1的情況。

因為當i為0時左邊不存在元素，沒比較的必要，i為2時右邊沒元素，也沒必要比較，所以我最初循環(huán)的條件為：

for (var i = 1; i < nums.length - 1; i++) {}

然后提交就掛掉了，提示應(yīng)該返回0而不是-1，也就是按照官方的理解，i為0時左邊雖然沒元素但和為0（我服了...）。

經(jīng)過修改這里提供我的實現(xiàn)，比較粗暴：

/**
 * @param {number[]} nums
 * @return {number}
 */
var pivotIndex = function(nums) {
  var i = 0,
    // 左邊的和
    sum_l = 0,
    // 右邊的和
    sum_r = 0,
    len = nums.length;
  for (; i < len; i++) {
    // 由于i從0開始，nums[0 - 1]為undefined，計算會讓結(jié)果變成NaN
    if(nums[i - 1]){
      sum_l += nums[i - 1];
    };
		// 截取i右邊的數(shù)組求和
    nums.slice(i + 1).map(item => {
      sum_r += item;
    });
    // 比較判斷，符合返回i
    if (sum_l == sum_r) {
      return i;
    } else {
      //每次比較完重置右邊的和，免得遍歷一次越來越大
      sum_r = 0;
    };
  };
  return -1;
};

提交一看時間，我人都傻了...

真是要了老命的算法，用了2S...

其實按照題目描述，我們可以知道數(shù)組所有元素的總和等于i+i左邊和+i右邊和，所以得出多種公式：

//左邊的和 = (總和 - i)除以2
sumLeft = (sum - i)/2
//或者
sumLeft = sum - i - sumLeft

貼上實現(xiàn)代碼：

/**
 * @param {number[]} nums
 * @return {number}
 */
var pivotIndex = function (nums) {
  var i = 0,
    len = nums.length,
    sum = 0,
    sumLeft = 0;
  // 求數(shù)組總和
  nums.map(item => sum += item);
  // 考慮左邊沒元素默認為0的情況，所以i為0時不進行sumLeft+=nums[i]的操作
  for (; i < len; i++) {
    if ((sum - nums[i]) / 2 === sumLeft) {
      return i;
    };
    sumLeft += nums[i];
  };
  return -1;
};

其實唯一需要注意的就是我前面說的坑，i為0時默認左邊為0，所以我們是判斷了一次后才執(zhí)行sumLeft += nums[i]。

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論