Menu Close

前缀和,你要跳舞吗?[Red Panda]

animal-2304712_960_720.jpg

标题灵感来自新裤子乐队《你要跳舞吗》,可以听听

1.和为K的子数组

1591023575858.png

方法1:基础版前缀和

  • pre[i]表示前i个数的前缀和即 nums[0...i-1]这个范围内的前缀和

方法2:Hashmap版前缀和

定义

  • pre[i]nums[0...i]里所有数的和,即为前缀和

560_1.jpg

  • 方框中的数字表示索引,pre[i]表示nums[0...i]这个区间内所有数的和,即这个区间的前缀和,如果出现红虚线框这种情况:nums[j...i]的和为K,那么很容易得到pre[j-1]=pre[i]-K
  • 建立map<Key,Value> ,其中Key表示是和,Value表示的是pre[i]这个前缀和出现的次数,注意初始化时,<0,1>,表示和为0时出现过1次,如nums=[2,4...]K=2, pre[0]=1

2.统计「优美子数组」

1591112688255.png

方法1:前缀和

定义

  • pre[i]nums[0...i]中奇数的个数,判断当前数是否是奇数的位运算:nums[i]&1,为0时表示奇数,同560的分析结果,很容易得到pre[j-1]=pre[i]-K,表示nums[j...i]范围内的奇数的个数恰好为K个,所以pre[i]的值只与pre[j-1]的值有关

  • 使用个长度为n+1的数组counter,记录的是pre[i]的个数,即数组范围nums[0...i]的奇数出现的次数,而counter[pre[i]]的值依赖于counter[pre[i]-K]的值,只有当pre[i]>K时才有意义

  • 初始化:counter[0]=1, 需要考虑这种边界情况: nums = [1,1] k = 2 , 遍历到i=1的索引位置时:

    res=counter[2-2]=counter[0]=1如果初始化为0时,过不了

复杂度分析

  • 时间复杂度:O(N), 一次遍历即可,N为数组大小

  • 空间复杂度:O(N), 数组counter的大小

推荐阅读


发表评论

电子邮件地址不会被公开。 必填项已用*标注

苏ICP备20029284号-1