Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

leetcode 413. 等差数列划分 #动态规划 #32

Open
webVueBlog opened this issue May 29, 2022 · 1 comment
Open

leetcode 413. 等差数列划分 #动态规划 #32

webVueBlog opened this issue May 29, 2022 · 1 comment

Comments

@webVueBlog
Copy link
Collaborator

image
413. 等差数列划分

@webVueBlog
Copy link
Collaborator Author

413. 等差数列划分

/*
 * @lc app=leetcode.cn id=413 lang=javascript
 *
 * [413] 等差数列划分
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
从第三个元素开始,判断以当前元素为结尾的三个数是不是等差数列
是,那么以当前为结尾的等差数组个数为 dp[i-1] + 1
不是,那么以当前数为结尾的等差数组的个数为 0

[1,2,3,4,5,6]
[1,2,3,4] [2,3,4]
[1,2,3,4,5] [2,3,4,5] [3,4,5]

dp[i] 以i为结尾的等差子数组的个数
(56 ms)
 */
var numberOfArithmeticSlices = function(A) {
    let sum = 0;
    dp = Array(A.length).fill(0);
    for (var i = 2; i <= dp.length - 1; i++) {
        if (A[i] - A[i - 1] === A[i - 1] - A[i - 2]) {
            dp[i] = 1 + dp[i - 1];
            sum += dp[i];
        }
    }
    return sum;
};
// @lc code=end

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant