leetcode：98. 统计得分小于 K 的子数组数目【双指针 + 计算子集个数 + 去重】

分析

滑动窗口得到所有合法的最大的【l， r】
如果排序后的区间有覆盖的部分需要剪掉覆盖的即可
因为大的区间成立，小的必然成立
所以用滑动窗口找到所有成立的大区间 再求子集 并相邻区间去重即可

Ac code

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        ans = 0
        n = len(nums)
        l = 0
        nowSum = 0
        nowLen = 0
        myDict = defaultdict(int)
        
        for r in range(n):
            nowSum += nums[r]
            nowLen += 1
            
            if nowSum * nowLen < k:
                myDict[l] = r
            
            else:
                 while nowSum * nowLen >= k:
                    nowSum -= nums[l]
                    nowLen -= 1
                    l += 1
                
                 myDict[l] = r
        
        myList = list(myDict.items())
        myList.sort()
        #print(myList)
        
        for l, r in myList:
            ans += ((r - l + 2) * (r - l + 1)) // 2
        
        for i in range(1, len(myList)):
            if myList[i][0] <= myList[i - 1][1]:
                l, r = myList[i][0], myList[i - 1][1]
                ans -= ((r - l + 2) * (r - l + 1)) // 2
        
        return ans
                        
            
        
        

            
            

总结

连续的这种东西滑动窗口永远是个思路
然后发现大的成立小的一定成立
计算一下区间内的子集总数
然后相邻区间去重一下即可