signed

QiShunwang

“诚信为本、客户至上”

413. Arithmetic Slices [Medium]

2021/5/14 20:13:47   来源:
/**
 * 自己的代码
 * 从第一个元素开始遍历找到以它开头的等差数列的长度(没有就再从下一个元素开始),向res中加上这段能组成的至少连续三个元素的subarray的数量
 * 再从上一段等差数列的最后一个元素开始找下一段等差数列,以此循环
 * Runtime: 0 ms, faster than 100.00% 
 * Memory Usage: 36.8 MB, less than 39.37%
 */
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int delta = nums[i] - nums[i + 1], cnt = 2;
            while (i < nums.length - 2 && nums[i + 1] == nums[i + 2] + delta) {
                cnt++;
                i++;
            }
            res += (cnt - 1) * (cnt - 2) / 2; // 计算cnt个连续元素的等差数列能组成的连续等差子数列个数
        }
        return res;
    }
}
/**
 * 不用dp数组的动态规划
 * preNums相当于dp[i - 1],dp[i]代表以第i个元素结尾的subarray的个数
 * Runtime: 0 ms, faster than 100.00%
 * Memory Usage: 36.6 MB, less than 71.89% 
 */
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int preNums = 0, res = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i - 1] - nums[i] == nums[i - 2] - nums[i - 1]) {
                preNums += 1; // 因为加上当前元素而增加的subarray数量(增加preNums个和之前对称的子数组,以及1个长了一位的总数组)
                res += preNums; // 将增加的subarray数量加到res中
            } else {
                preNums = 0; // 没有当前元素结尾的subarray
            }
        }
        return res;
    }
}