[LeetCode 题号] 题目名

[LeetCode 题号] 题目名题目描述给你一个整数数组nums和一个整数target。统计并返回nums中其元素target的出现次数严格大于子数组长度的一半的子数组数目。示例 1输入nums [2,1,3,1,1], target 1输出4解释长度为 1 的子数组[1]出现了 1 次1 1/2满足条件。长度为 3 的子数组[1,3,1]出现了 2 次2 3/2满足条件。长度为 5 的子数组[2,1,3,1,1]出现了 3 次3 5/2满足条件。长度为 4 的子数组[1,3,1,1]出现了 2 次2 4/2 不满足等于一半不是严格大于。最终满足条件的子数组共有 4 个。示例 2输入nums [0,0,0], target 1输出0解释target在数组中从未出现所以没有满足条件的子数组。提示1 nums.length 10000 nums[i], target 1000解题思路看数据范围nums.length 1000这基本就是明示你可以用O(n²) 的暴力枚举。思路很简单枚举所有可能的子数组起点i从 0 到 n-1从起点i开始向右扩展终点j在扩展过程中维护target的出现次数对于每个子数组nums[i..j]检查target的出现次数是否严格大于子数组长度的一半即target_count (j - i 1) // 2满足条件则计数器加 1时间复杂度O(n²)两层循环枚举所有子数组空间复杂度O(1)只用了常数个变量完整代码class Solution: def countSubarrays(self, nums: List[int], target: int) - int: n len(nums) count 0 for i in range(n): target_count 0 for j in range(i, n): if nums[j] target: target_count 1 # 子数组长度为 j - i 1 if target_count (j - i 1) // 2: count 1 return count复杂度分析时间复杂度O(n²)其中 n 是数组nums的长度。我们需要枚举所有可能的子数组共有 O(n²) 个子数组对于每个子数组我们在扩展终点时维护target的计数因此总时间复杂度为 O(n²)。空间复杂度O(1)只使用了常数个额外变量。