Easy
题目描述
给定一个整数数组 nums，返回长度为 3 的子数组的数量，使得第一个和第三个数字的和恰好等于第二个数字的一半。
示例 1:
输入: nums = [1,2,1,4,1]
输出: 1
解释: 只有子数组 [1,4,1] 包含恰好 3 个元素，其中第一个和第三个数字的和等于中间数字的一半。
示例 2:
输入: nums = [1,1,1]
输出: 0
解释: [1,1,1] 是唯一长度为 3 的子数组。然而，它的第一个和第三个数字的和不等于中间数字的一半。
提示:
3 <= nums.length <= 100-100 <= nums[i] <= 100
解题思路
这道题目要求找到满足特定条件的长度为 3 的子数组，条件是：第一个元素 + 第三个元素 = 第二个元素的一半。
解题思路：
由于数组长度最大只有 100，我们可以使用简单的暴力遍历方法。对于每个可能的起始位置 i，检查子数组 [nums[i], nums[i+1], nums[i+2]] 是否满足条件。
关键点分析：
- 条件转换：
nums[i] + nums[i+2] = nums[i+1] / 2 - 为避免浮点运算，可以将条件改写为：
2 * (nums[i] + nums[i+2]) = nums[i+1] - 遍历范围：从索引 0 到
nums.length - 3，因为需要保证有足够的元素构成长度为 3 的子数组
算法步骤：
- 初始化计数器
count = 0 - 遍历所有可能的起始位置
i（从 0 到n-3） - 对每个位置，检查是否满足条件：
2 * (nums[i] + nums[i+2]) == nums[i+1] - 如果满足条件，计数器加 1
- 返回最终计数
这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，在给定的约束条件下非常高效。
代码实现
class Solution {
public:
int countSubarrays(vector<int>& nums) {
int count = 0;
int n = nums.size();
for (int i = 0; i <= n - 3; i++) {
if (2 * (nums[i] + nums[i + 2]) == nums[i + 1]) {
count++;
}
}
return count;
}
};
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
count = 0
n = len(nums)
for i in range(n - 2):
if 2 * (nums[i] + nums[i + 2]) == nums[i + 1]:
count += 1
return count
public class Solution {
public int CountSubarrays(int[] nums) {
int count = 0;
int n = nums.Length;
for (int i = 0; i <= n - 3; i++) {
if (2 * (nums[i] + nums[i + 2]) == nums[i + 1]) {
count++;
}
}
return count;
}
}
var countSubarrays = function(nums) {
let count = 0;
for (let i = 0; i <= nums.length - 3; i++) {
if (nums[i] + nums[i + 2] === nums[i + 1] / 2) {
count++;
}
}
return count;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要遍历数组一次，其中 n 是数组长度 |
| 空间复杂度 | O(1) | 只使用了常数个额外变量 |