# LeetCode Easy 724. Find Pivot Index

tags: leetcode

志望度の高かったインターンに落ちて気持ちが萎えています．でも逆にやりたいことがはっきりしました．

問題

• Explore
• Problems

アイデア

ある要素よりも左の要素の和と右の要素の和が等しい要素のindexを返せという問題です．

解法

最初に配列を全て足し合わせます(C++ならstd::accumulateが便利です)．この和をsumとします．

次に，pivotとなる部分までを左から足した値をleft_sumとして2 * left_sum - nums[pivot] == sumとなるはずです．

下の図のようにpivotを境にした左(赤)と右(青)の和は等しいので，2 * left_sumはred + blue + 2 * pivotと等しいです

計算量

配列の大きさを$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  int pivotIndex(vector<int>& nums) {
    auto sum = accumulate(nums.begin(), nums.end(), 0);
    auto left_sum = 0;
    for (int pivot = 0; pivot < nums.size(); pivot++) {
      left_sum += nums[pivot];
      if (2 * left_sum - nums[pivot] == sum)
        return pivot;
    }
    return -1;
  }
};