配列 / 文字列（応用）累積和（Prefix Sum）

部分配列の和と聞いたら累積和を使えないか考える

累積和を利用して任意の区間の和を計算する

Maximum Score After Splitting a String

class Solution:
    def maxScore(self, s: str) -> int:
        cumulative_zero_count = [1 if s[0] == "0" else 0]
        cumulative_one_count = [1 if s[0] == "1" else 0]
        for i in range(1, len(s)):
            if s[i] == "0":
                cumulative_zero_count.append(cumulative_zero_count[-1] + 1)
                cumulative_one_count.append(cumulative_one_count[-1])
            else:
                cumulative_zero_count.append(cumulative_zero_count[-1])
                cumulative_one_count.append(cumulative_one_count[-1]+1)
        ans = 0
        for i in range(len(s)-1):
            zero_count = cumulative_zero_count[i]
            one_count = cumulative_one_count[-1] - cumulative_one_count[i]
            ans = max(ans, zero_count + one_count)
        return ans

0と1の個数を累積で数えておくだけ.
let n the length of s.
time complexity:O(n)
time complexity:O(n)

Product of Array Except Self

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        leftNums = [1]
        for i in range(len(nums)-1):
            leftNums.append(nums[i]*leftNums[-1])
        
        rightNums = [1]*len(nums)
        for i in range(len(nums)-1, 0, -1):
            rightNums[i-1] = nums[i]*rightNums[i]
        
        ans = [1]*len(nums)
        for i in range(len(nums)):
            ans[i] = leftNums[i]*rightNums[i]
        return ans

time complexity:O(n)
space complexity:O(n)

Sum of Absolute Differences

簡単

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        cumulative = [nums[0]]
        for i in range(1, len(nums)):
            cumulative.append(cumulative[-1] + nums[i])
        ans = [0]*len(nums)
        n = len(nums)
        for i in range(n):
            v = nums[i]
            # ans[i]を求める
            # v * i - 0~i-1の和
            sum = 0
            if i >= 1:
                sum += v * i - (cumulative[i-1])
            sum += (cumulative[n-1]-cumulative[i]) - v * (n-1-i)
            ans[i] = sum
        return ans

Maximum Good Subarray Sum

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        dic = {}
        ans = -float('inf')

        cumulative = [0]
        for i in range(len(nums)):
            cumulative.append(nums[i] + cumulative[-1])
        
        for i,n in enumerate(nums):
            # i - nums[n] = +-k 
            if (k + nums[i]) in dic:
                # calculate i ~ j
                j = dic[k+nums[i]]
                if i > j:
                    ans = max(ans, cumulative[i+1] - cumulative[j])
                else:
                    ans = max(ans, cumulative[j+1] - cumulative[i])

            if (-k + nums[i]) in dic:
                j = dic[-k+nums[i]]
                if i > j:
                    ans = max(ans, cumulative[i+1] - cumulative[j])
                else:
                    ans = max(ans, cumulative[j+1] - cumulative[i])
            if nums[i] in dic:
                j = dic[nums[i]]
                if cumulative[i] - cumulative[j] < 0: 
                    dic[nums[i]] = i
            else:
                dic[nums[i]] = i

        return ans if ans != -float('inf') else 0

同じ数字が来たときに、更新するか否かのif文だけ注意.

累積和をキーとして利用する

Subarray Sum Equals K

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = defaultdict(int)
        dic[0] = 1
        cumu_sum = 0
        ans = 0
        for n in nums:
            cumu_sum += n
            if cumu_sum - k in dic:
                ans += dic[cumu_sum - k]
            dic[cumu_sum] += 1

        return ans

Subarray Sums Disible by K

from collections import defaultdict

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        cumu_sum = 0
        dic = defaultdict(int)
        dic[0] = 1
        ans = 0

        for n in nums:
            cumu_sum += n
            if (cumu_sum) % k in dic:
                ans += dic[(cumu_sum) % k]
            dic[(cumu_sum) % k] += 1
        return ans

累積和の余りをハッシュで管理. あまりがハッシュにあれば、kで割り切れる部分和が存在するってこと.