【LeetCode】 724. Find Pivot Index 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, 愚直解
  2. 解答2：Python
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- 累積和

詳細

問題

原文

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.

Example 1:

Input: nums = [1,7,3,6,5,6] Output: 3 Explanation: The pivot index is 3. Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 Right sum = nums[4] + nums[5] = 5 + 6 = 11

1
2
3
4
5
6

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3] Output: -1 Explanation: There is no index that satisfies the conditions in the problem statement.

1
2
3
4

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1] Output: 0 Explanation: The pivot index is 0. Left sum = 0 (no elements to the left of index 0) Right sum = nums[1] + nums[2] = 1 + -1 = 0

1
2
3
4
5
6

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints:

1 <= nums.length <= 10⁴

-1000 <= nums[i] <= 1000

内容(和訳)

整数の配列 nums が与えられると、この配列のピボットインデックスを計算してください。

ピボットインデックスは、インデックスの左側のすべての数字の合計が、インデックスの右側のすべての数字の合計と等しいインデックスです。

インデックスが配列の左端にある場合、左側の合計は 0 になります。

これは、配列の右端にも適用されます。

左端のピボットインデックスを返してください。

そのようなインデックスが存在しない場合は、-1 を返します。

※Bardによる翻訳

解答

解答1：Python, 愚直解

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            left_sum = sum(nums[:i])
            right_sum = sum(nums[i+1:])
            if left_sum == right_sum:
                return i
        return -1

class Solution:

def pivotIndex(self, nums: List[int]) -> int:

for i in range(len(nums)):

left_sum = sum(nums[:i])

right_sum = sum(nums[i+1:])

if left_sum == right_sum:

return i

return -1

iが進むたびに左側と右側の合計を計算しなおしている。

スライスを使った操作は計算量がO(n)だった気がするので、

時間計算量はforループO(n)と都度の合計値を求める操作O(n)の掛算なので、O(n^2)？

解答2：Python

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left_sum = 0
        right_sum = sum(nums)
        previous_element = 0

        for i in range(len(nums)):    
            left_sum += previous_element
            right_sum -= nums[i]
            if left_sum == right_sum:
                return i
            previous_element = nums[i]
        
        return -1

class Solution:

def pivotIndex(self, nums: List[int]) -> int:

left_sum = 0

right_sum = sum(nums)

previous_element = 0

for i in range(len(nums)):

left_sum += previous_element

right_sum -= nums[i]

if left_sum == right_sum:

return i

previous_element = nums[i]

return -1

初期状態の左側の合計と右側の合計値を求めておき、iが進むたびに左と右の合計値を求めなおす。

具体的には、前回のループ時の値をprevious_elementに保持しておき、

今回のループでは、左側の合計値に加算、右側の合計値から減算する。

こうすることで、スライスを使った合計値を求める必要がなくなり、時間計算量はO(n)、

配列は用意していないので定数空間の空間計算量になる…はず。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：1732. Find the Highest Altitude

次：1207. Unique Number of Occurrences

LeetCode 解答・解説記事一覧