LeetCode: 413. Arithmetic Slices 数组中等差子序列的个数

分手后的思念是犯贱 2021-06-24 16:10 405阅读 0赞

**试题：**  
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9  
7, 7, 7, 7  
3, -1, -5, -9  
The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:  
A\[P\], A\[p + 1\], …, A\[Q - 1\], A\[Q\] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = \[1, 2, 3, 4\]

return: 3, for 3 arithmetic slices in A: \[1, 2, 3\], \[2, 3, 4\] and \[1, 2, 3, 4\] itself.

**代码：**  
dp\[i\]仅是存储以A\[i\]结尾的等差数列。从dp\[i-1\]到dp\[i\]，一种是dp\[i-1\]已经保存的，另外就是新加一个。  
此处动态规划求解了每个位置结尾的子序列数量，最终结果还需要求和。

class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            if(A==null || A.length==0) return 0;
            int len = A.length;
            int[] dp = new int[len];
            
            for(int i=2; i<len; i++){
                if(A[i]-A[i-1]==A[i-1]-A[i-2]){
                    dp[i] = dp[i-1] + 1;
                }
            }
            
            int total=0;
            for(int num : dp){
                total += num;
            }
            return total;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，405人围观）

还没有评论，来说两句吧...

相关阅读

相关 1630. 等差子数组

如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是等差数列。更正式地，数列 `s` 是等差数列，只需要满足：对于每个有效的 `i` ， `s

本是古典何须时尚/ 2023年10月04日 08:12/ 0 赞/ 9 阅读

相关 Arithmetic Subarrays（C++等差子数组）

解题思路：（1）截取子数组，排序 class Solution { public: bool Judge(vector<

短命女/ 2022年12月31日 05:17/ 0 赞/ 155 阅读

相关 1630. 等差子数组

[https://leetcode-cn.com/problems/arithmetic-subarrays/][https_leetcode-cn.com_problems_

待我称王封你为后i/ 2022年09月06日 16:13/ 0 赞/ 137 阅读

相关 leetcode 413. Arithmetic Slices | 413. 等差数列划分（Java）

题目 [https://leetcode.com/problems/arithmetic-slices/][https_leetcode.com_problems_ari

短命女/ 2022年09月02日 11:39/ 0 赞/ 160 阅读

相关 413. Arithmetic Slices （找等差数列）

A sequence of number is called arithmetic if it consists of at least three elements and

àì夳堔傛蜴生んèń/ 2022年07月15日 08:14/ 0 赞/ 154 阅读

相关 [leetcode]--413. Arithmetic Slices

Question 413. Arithmetic Slices > A sequence of number is called arithmetic if it consi

刺骨的言语ヽ痛彻心扉/ 2022年07月11日 23:24/ 0 赞/ 150 阅读

相关 leetcode 413. Arithmetic Slices

1.题目 A sequence of number is called arithmetic if it consists of at least three eleme

深藏阁楼爱情的钟/ 2022年06月13日 01:19/ 0 赞/ 166 阅读

相关 leetcode 413. Arithmetic Slices 等差子数组 + 一个很简单DP动态规划做法

A sequence of number is called arithmetic if it consists of at least three elements and

绝地灬酷狼/ 2022年06月04日 08:14/ 0 赞/ 176 阅读

相关 413. Arithmetic Slices

[413. Arithmetic Slices][] A sequence of number is called arithmetic if it consists of

Love The Way You Lie/ 2021年09月30日 07:46/ 0 赞/ 235 阅读

相关 LeetCode: 413. Arithmetic Slices 数组中等差子序列的个数

试题： A sequence of number is called arithmetic if it consists of at least three element

分手后的思念是犯贱/ 2021年06月24日 16:10/ 0 赞/ 406 阅读