1667. 区间统计（回顾）

1667. 区间统计

CAT 专属题目

中文English

给定一个01数组 arr 和 一个整数 k, 统计有多少区间符合如下条件:

1. 区间的两个端点都为 0 (允许区间长度为1)
2. 区间内 1 的个数不多于 k

样例

样例 1:

输入: arr = [0, 0, 1, 0, 1, 1, 0], k = 1
输出: 7
解释: [0, 0], [1, 1], [3, 3], [6, 6], [0, 1], [0, 3], [1, 3] (区间 [i，j] 表示下标 i（包括）和下标 j（包括）之间的元素)

样例 2:

输入: arr = [1, 1, 1, 0, 0, 1], k = 2
输出: 3
解释: [3, 3], [4, 4], [3, 4] (区间 [i，j] 表示下标 i（包括）和下标 j（包括）之间的元素)

注意事项

arr 的大小不超过 10^5

 

 

输入测试数据 (每行一个参数)如何理解测试数据？

 同向型双指针：

class Solution:
    """
    @param arr: the 01 array
    @param k: the limit 
    @return: the sum of the interval
    """
    def intervalStatistics(self, arr, k):
        # Write your code here.
        #首先right走到0的位置，然后left也走到的位置，计算之间1的个数，如果大于k，则left += 1,一直到符合为止
        
        length = len(arr)
        left, right = 0, 0 
        numofone = 0 
        count = 0 
        
        while right < length:
            #首先right走到0的位置
            if (arr[right] == 1):
                numofone += 1 
                right += 1 
                continue
            
            #然后left走到0的位置
            if (arr[left] == 1):
                numofone -= 1 
                left += 1 
                continue
            
            #此时right和left均在0的位置,判断如果numofone大于k,则left走到numofone小于k的时候为止
            while numofone > k:
                if (arr[left] == 1):
                    numofone -= 1 
                left += 1 
            
            #此时numofone满足条件,如果当前值为0,left = right ，numofone为0，则加1
            #如果left != right，则加 + left到right之间为0的个数，即 -numofone，[left, right]
            count = right - left + 1 + count - numofone
            right += 1 
        
        return count