1.1前言：

本文將詳細(xì)講解itertools中的accumulate，accumulate函數(shù)可以在前綴和中運(yùn)用，否則就需要每次移動(dòng)的時(shí)候維護(hù)一個(gè)前綴和，大家如果不知道前綴和也可以先了解一下前綴和，前綴和可以解決數(shù)組區(qū)間和查詢(xún)問(wèn)題、矩陣區(qū)域和查詢(xún)問(wèn)題、連續(xù)子數(shù)組和問(wèn)題、最大子段和問(wèn)題、最大子矩陣和問(wèn)題這里，但是如果大家不太了解前綴和也可以放心食用，因?yàn)檫\(yùn)用這個(gè)累加函數(shù)其實(shí)十分簡(jiǎn)單。

1.2定義：

itertools. accumulate(iterable[,function,*,initial = None])

創(chuàng)建一個(gè)返回累積匯總值或來(lái)自其他雙目運(yùn)算函數(shù)的累積結(jié)果的迭代器。function 默認(rèn)為加法運(yùn)算。 function 應(yīng)當(dāng)接受兩個(gè)參數(shù)，即一個(gè)累積匯總值和一個(gè)來(lái)自 iterable 的值。如果提供了 initial 值，將從該值開(kāi)始累積并且輸出將比輸入可迭代對(duì)象多一個(gè)元素。

大家也可以自行實(shí)現(xiàn)前綴和，第一種是簡(jiǎn)易寫(xiě)法，這種寫(xiě)法其實(shí)已經(jīng)滿(mǎn)足很多前綴和的題目了，

pre_num = [0]
#由于為了滿(mǎn)足前綴和的性質(zhì)第一個(gè)數(shù)一定要置零才能滿(mǎn)足所有的數(shù)都可以由兩個(gè)前綴和來(lái)表示
for idx,x in enumerate(nums):
 
    pre_num.append(pre_num[idx] + x)

accumulate大致相當(dāng)于： 

def accumulate(iterable, function=operator.add, *, initial=None):
    'Return running totals'
    # accumulate([1,2,3,4,5]) → 1 3 6 10 15
    # accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 115
    # accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 120

    iterator = iter(iterable)
    total = initial
    if initial is None:
        try:
            total = next(iterator)
        except StopIteration:
            return

    yield total
    for element in iterator:
        total = function(total, element)
        yield total

 值得注意的是如下用法放回的是地址而不是元素的值

temp = itertools.accumulate([1,2,3,4,5,6], initial = 0)

##結(jié)果：<itertools.accumulate object at 0x00000193FA04D990>

如果要返回元素的值還需要如下操作: 

temp = list(itertools.accumulate([1,2,3,4,5,6], initial = 0))

1.3衍生用法：

剛才我們也提到了accumulate里面有個(gè)參數(shù)是function，這個(gè)函數(shù)默認(rèn)是累加方法，但是用戶(hù)也可以自己自己設(shè)定方法，比如max , min,等其他。

data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
list(accumulate(data, max))              # 運(yùn)行最大值
##結(jié)果[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]

list(accumulate(data, operator.mul))     # 運(yùn)行乘積
##結(jié)果[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]

##題目： 分期償還利率 5% 總額 1000 的貨款，每年還款 10 次，每次 90
update = lambda balance, payment: round(balance * 1.05) - payment
list(accumulate(repeat(90, 10), update, initial=1_000))
##結(jié)果[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]

1.3Leetcode的實(shí)際運(yùn)用:

Eg1:使數(shù)組元素全部相等的最少操作次數(shù)：

給你一個(gè)正整數(shù)數(shù)組 nums 。同時(shí)給你一個(gè)長(zhǎng)度為 m 的整數(shù)數(shù)組 queries 。第 i 個(gè)查詢(xún)中，你需要將 nums 中所有元素變成 queries[i] 。你可以執(zhí)行以下操作 任意 次：

• 將數(shù)組里一個(gè)元素 增大 或者 減小 1 。

請(qǐng)你返回一個(gè)長(zhǎng)度為 m 的數(shù)組 answer ，其中 answer[i]是將 nums 中所有元素變成 queries[i] 的 最少 操作次數(shù)。

注意，每次查詢(xún)后，數(shù)組變回最開(kāi)始的值。

示例 1：

輸入：nums = [3,1,6,8], queries = [1,5]

輸出：[14,10]

解釋?zhuān)?/strong>第一個(gè)查詢(xún)，我們可以執(zhí)行以下操作：
- 將 nums[0] 減小 2 次，nums = [1,1,6,8] 。
- 將 nums[2] 減小 5 次，nums = [1,1,1,8] 。
- 將 nums[3] 減小 7 次，nums = [1,1,1,1] 。
第一個(gè)查詢(xún)的總操作次數(shù)為 2 + 5 + 7 = 14 。
第二個(gè)查詢(xún)，我們可以執(zhí)行以下操作：
- 將 nums[0] 增大 2 次，nums = [5,1,6,8] 。
- 將 nums[1] 增大 4 次，nums = [5,5,6,8] 。
- 將 nums[2] 減小 1 次，nums = [5,5,5,8] 。
- 將 nums[3] 減小 3 次，nums = [5,5,5,5] 。
第二個(gè)查詢(xún)的總操作次數(shù)為 2 + 4 + 1 + 3 = 10 。

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        s = list(accumulate(nums,initial = 0)) ##前綴和
        ans = []
        for q in queries:
            j = bisect_left(nums, q) 
            left = q * j - s[j] #藍(lán)色面積
            right = s[n] - s[j] - q*(n - j) #綠色的面積
            ans.append(left + right)
        return ans

from itertools import accumulate

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        #前綴和的知識(shí)，注意前綴和s[0] == 0 這樣定義有一個(gè)好處就是任意子數(shù)組包括前綴哦都可以表示為兩個(gè)前綴和的差
        #中位數(shù)貪心，將所有元素變?yōu)閚ums的中位數(shù)是最優(yōu)
        nums.sort()##最開(kāi)始忘了要排序
        pre_sum = list(accumulate(nums, initial = 0))
        #由于第一個(gè)數(shù)字是零所以整個(gè)長(zhǎng)度就是n + 1
        def distance_sum(left , right) -> int:
            mid = ( right + left ) // 2
            left_sum = nums[mid] * (mid - left) - (pre_sum[mid] - pre_sum[left]) 
            right_sum = pre_sum[right+1] - pre_sum[mid+1] - (right - mid) * nums[mid]
            return left_sum + right_sum

        left = ans = 0              #滑動(dòng)窗口
        for right  in range(len(nums)):
            while distance_sum(left,right) > k :
                left += 1
            ans = max(ans,right - left + 1)
        return ans