leetcode

leetcode--前缀和

Posted by PNIDEMOOO on 2021-01-21

leetcode算法–前缀和

一维前缀和

举例：
假设一维数组为a=[1,4,6,2,7]
前缀和数组sums=[1,5,11,13,20]
求第2个元素“6”到第4个元素“7”之间的和（左开右闭），即可用sums[4]-sums[2]=9

“前缀和”是一种思想，并不是一定要求“和”，也可以是其他值，只要满足f(i,j)=f(j)-f(i)即可，其中f(i,j)表示第i到第j个元素之间的某值，f(i)表示第i个元素之前的某值。

例题：Leetode 1248 统计「优美子数组」

题目描述

给你一个整数数组nums和一个整数k。
如果某个连续子数组中恰好有k个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。

示例

示例 1： 

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2： 

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例3： 

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

提示

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

解题思路

数据范围在50000以下，对照 做题顺序
中的 数据范围 => 时间复杂度 => 算法集合 ，得出算法集合：

差分、前缀和、双指针、桶排序、单调栈、单调队列

再看本题特征：

  • 连续子数组
  • 子数组内恰好有k个奇数数字

可得出结论：本题可用前缀和思想求解。

如果对「前缀和」算法有所掌握的话，凭借这两大特征不难确定此题可以用「前缀和」求解。

设原数组为 nums=[2,1,3,4,6,8,7,10,12,5,14], k=3：

index 0 1 2 3 4 5 6 7 8 9 10
value 2 1 3 4 6 8 7 10 12 5 12

令 sums[i+1] 表示数组第 0 个数到第 i 个数中奇数的个数。sums[0]=0，这里为什么要补一个sums[0]在后边会讲。则在此例中，sums数组应为：

index 0 1 2 3 4 5 6 7 8 9 10 11
value 0 0 1 2 2 2 2 3 3 3 4 4

这个sums数组有什么用呢？

对于此例的nums=[2,1,3,4,6,8,7,10,12,5,14], k=3来说，对于包含1,3,7这三个连续奇数的所有连续子数组，[1,3,4,6,8,7]是其中长度最小的一个。再扩大长度，可以将1的左边延伸到最后一个非奇数，将7的右边延伸到最后一个非奇数。也就是说，最长的就是[2,1,3,4,6,8,7,10,12]。只要包含[1,3,4,6,8,7]，最左可以是1或2，共2种选择，左右可以是7或10或12共3种选择，也就是说，包含1,3,7这三个连续奇数的所有连续子数组共有 2 × 3 = 6 个。

总结：假设原数组中，共有n个奇数： 0,1,…,a-1,a,…,b,b+1,…,n。
包含 第a个奇数…第b个奇数 的连续子数组共有：(a-1,a]的长度 × [b,b+1)的长度。

又因为：
（1）[b,b+1)的长度就等于sums数组中值为b+1的元素的个数；
（2）当a>=1时，(a-1,a]的长度等于[a-1,a)的长度，就等于sums数组中值为a的元素的个数；为了让a=0时也符合要求，就给sums数组最前边补一个值为0的元素，即sums[0]=0。

因此，新建一个sums_value数组，用来记录sums数组中每个值的个数。则在此例中，sums_value数组应为：

index 0 1 2 3 4
value 2 1 4 3 2

对于i>=k，所有sums_value[i]×sums_value[i-k]的和即为本题最终结果。

注意：在编码过程中sums数组无需出现，sums_value数组无需在得出完整sums数组后再赋值。sums数组只是为了便于理解。

代码

class Solution:
    # 前缀和思想
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        subarrays_count=0 # 完美子数组的个数
        # sums=[] # sum[i]表示在数组nums中，第i-1个元素(不包括第i-1个)之前有多少个奇数
        # sums.append(0)
        sum_count=0 
        sums_value=[] # sums_value[i]表示sums的元素中值为i的个数
        sums_value.append(1)
        value=0
        for i in range(1,len(nums)+1):
            if(nums[i-1]%2==1):
                sum_count=sum_count+1
                value=value+1
                sums_value.append(1)
            else:
                sums_value[value]=sums_value[value]+1
            # sums.append(sum_count)
        for j in range(len(sums_value)):
            if j-k>=0:
                subarrays_count=subarrays_count+sums_value[j-k]*sums_value[j]
        # print("sums=",sums)
        # print("sums_value",sums_value)
        return (subarrays_count)

题目来源

leetcode 1248 统计「优美子数组」

FEATURED TAGS
leetcode
FRIENDS