【LeetCode】 1588. Sum of All Odd Length Subarrays 解答・解説【Python】

はじめに
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python
終わりに
1. 補足・参考・感想
2. 疑問が解決した方はこちらへ

はじめに

LeetCodeの問題を解答します。

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

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

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

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

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

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

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

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

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

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

ポイント

愚直な方法で解答します。

この記事で得られること

ステップを指定したfor文の使い方
O(n^3)の解答

この記事が役立ちそうな方

ステップを指定したfor文の使い方を練習したい方

詳細

問題

原文

Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: arr = [1,4,2,5,3] Output: 58 Explanation: The odd-length subarrays of arr and their sums are: [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,2] = 7 [4,2,5] = 11 [2,5,3] = 10 [1,4,2,5,3] = 15 If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

1
2
3
4
5
6
7
8
9
10
11
12
13

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2] Output: 3 Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

1
2
3

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12] Output: 66

1
2

Input: arr = [10,11,12]
Output: 66

Constraints:

1 <= arr.length <= 100

1 <= arr[i] <= 1000

内容(和訳)

正の整数配列arrが与えられるので、全ての奇数個の部分配列の合計を返してください。

subarrayは連続する部分配列のことです。

※正しくない可能性があります。

解答

解答1：Python

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        #解答用の変数
        answer = 0
        #各要素を一巡して走査する
        for i in range(len(arr)):
            #1要素,3要素,5要素のように1個飛ばしで要素数を増やしながら奇数個の部分配列を作る。
            #arrの要素が偶数の場合でも、その1つ前の奇数個までの部分配列を取れれば良い。
            for j in range(i,len(arr),2):
                #answerに奇数個の部分配列を追加
                answer += sum(arr[i:j+1])
        #answerを返す
        return answer<span style="background-color: #ffffff; font-family: 'Yu Gothic', Meiryo, 'Hiragino Kaku Gothic ProN', 'Hiragino Sans', sans-serif; font-size: 18px;"> </span>

class Solution:

def sumOddLengthSubarrays(self, arr: List[int]) -> int:

#解答用の変数

answer = 0

#各要素を一巡して走査する

for i in range(len(arr)):

#1要素,3要素,5要素のように1個飛ばしで要素数を増やしながら奇数個の部分配列を作る。

#arrの要素が偶数の場合でも、その1つ前の奇数個までの部分配列を取れれば良い。

for j in range(i,len(arr),2):

#answerに奇数個の部分配列を追加

answer += sum(arr[i:j+1])

#answerを返す

return answer<span style="background-color: #ffffff; font-family: 'Yu Gothic', Meiryo, 'Hiragino Kaku Gothic ProN', 'Hiragino Sans', sans-serif; font-size: 18px;"> </span>

for文2つにsum関数を使っているので、時間計算量がO(n^3)です。

改善の余地があります。