文章

[LeetCode] 每日一题 3392. 统计符合条件长度为 3 的子数组数目(简单题)

题目描述

给你一个整数数组 nums ,请你返回长度为 3 的 子数组 的数量,满足第一个数和第三个数的和恰好为第二个数的一半。

子数组 指的是一个数组中连续 非空 的元素序列。

子数组

子数组 是数组中连续的 非空 元素序列。

题目链接

https://leetcode.cn/problems/count-subarrays-of-length-three-with-a-condition

示例输入

示例 1

输入:nums = [1,2,1,4,1]

输出:1

解释:

只有子数组 [1,4,1] 包含 3 个元素且第一个和第三个数字之和是中间数字的一半。number.

示例 2

输入:nums = [1,1,1]

输出:0

解释:

[1,1,1] 是唯一长度为 3 的子数组,但第一个数和第三个数的和不是第二个数的一半。

提示

  • 3 <= nums.length <= 100

  • -100 <= nums[i] <= 100

解题思路

今天这道题目算是非常简单的一道题,题目要求我们统计所有长度为 3 的子数组,满足第一个数和第三个数的和恰好为第二个数的一半。

这类题目最直观的解法就是 按顺序遍历 数组,对于每个长度为 3 的子数组,检查是否符合题目要求。具体来说,对于一个子数组 [nums[i-2], nums[i-1], nums[i]],我们需要检查是否满足nums[i-2] + nums[i] == 2 * nums[i-1]

这里的 2 * nums[i-1] 是为了避免使用除法操作,因为在整数运算中直接使用除法可能会出现向下取整的问题,从而导致错误的结果。

代码实现

class Solution {
    public int countSubarrays(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (2 * (nums[i] + nums[i - 2]) == nums[i - 1]) {
                ans++;
            }
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度:O(n)

    • 需要遍历一次数组,从 i = 2 开始,检查每个长度为 3 的子数组,因此时间复杂度是线性的

  • 空间复杂度:O(1)

    • 只用了常数的额外空间来存储答案和变量,空间复杂度为常数

总结

这道题目非常简单,主要考察的是如何正确理解题目要求以及避免整数除法可能带来的误差。
这道题可以帮助我们巩固基础的遍历技巧,同时提醒我们在整数运算中避免直接使用除法,尤其是在涉及偶数和奇数的情况下。总体思路简单,适合快速刷题。

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0