LeetCode——413. 等差数列划分(Java)

题目描述

题干:
如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。
例如,[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。

示例 1:
输入:nums = [1,2,3,4]
输出:3
解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2:
输入:nums = [1]
输出:0

题解思路

返回等差子数组的个数,这里的等差数列是长度不能小于3个元素

自己首先想到的就是双指针或者滑动窗口,但是问题是如何控制每一个子数组的长度是一个问题

因为每次不成等差数列之后,如何再找到新的数列头呢,如果顺序判断则过度耗费时间

所以关键就是因为最低是三个元素,所以你只需要判断前一个的差和现在的差即可

于是我们可以倒着进行计算插值,只需要每次保留 n - 1 和 n - 2 的差和 n 和 n - 1 的差即可

正确代码

        int n = nums.length;
        if (n < 3) {
            return 0;
        }
        int d = nums[0] - nums[1], t = 0, ans = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i - 1] - nums[i] == d) {
                t++;
            } else {
                d = nums[i - 1] - nums[i];
                t = 0;
            }
            // 考虑到子数组可以继续分成子数组的情况
            ans += t;
        }
        return ans;

总结

这里最关键的就是想到倒序取得等差序列的差值,想想如果这是等比数列还能继续如此吗

如果文章存在问题或者有更好的题解,欢迎在评论区斧正和评论,各自努力,你我最高处见
上一篇:【《Hacker与画家》读厚】第一章 为什么书呆子不受欢迎——Paul眼里的学校 & 痛苦的根源


下一篇:linux – Dropbear会立即丢弃DD-WRT上的连接