413. Arithmetic Slices 等差数列划分

本文主要是介绍413. Arithmetic Slices 等差数列划分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode-cn.com/problems/arithmetic-slices/description/

思路:题目很冗长,实际上就是找有几个等差数列(长度大于3的).i作为序列头,从0开始到N-3遍历数组,首先找一个最短的等差序列(长度为3),找到后算出间距dist,再以j为序列尾,从i+3开始到N向后扩张,看等差序列是否还存在后续.只要找到一个间距不等于dist,表明在这里断开,退出内层j循环,序列头后移一位.如此往复

int numberOfArithmeticSlices(vector<int>& A) {int N = A.size();int count = 0;if (N < 3) return 0; //特殊情况处理for (int i = 0; i < N-2; i++) { //遍历0到N-3的位置if (A[i+1] - A[i] != A[i+2] - A[i+1]) continue;  //A[i,i+1,i+2]不满足等差数列,直接跳过本次循环int dist = A[i+1] - A[i];  //等差间距distancecount++;  //找到一个等差for (int j = i+3; j < N; j++) {  //j从i+2之后找,看等差序列是否还存在后续if (A[j] - A[j-1] != dist) break;  //只要发现一个不等的,立即退出循环count++;}}return count;
}

dp：见sulution动图解释。状态方程：dp[i] = dp[i-1]+1，dp[i]表示在i位置结尾的序列所含有的等差数列个数。
推导：

A[a...i]  #以i结尾的等差个数为dp[i]，若满足A[i+1]-A[i] == A[i]-A[i-1]
则序列：
A[a...i+1]  #以i+1结尾的等差个数为dp[i]+1，多出的一个以i+1结尾的序列为A[i-1...i+1]，长度为3

A[a...i]
A[a...i+1]
a到i的等差数列总个数为sum
则若dp[i]!=0，a到i+1的总个数为sum+dp[i]
理解：序列多了A[i+1]，此前的所有情况都增加1，即等差数列总个数增加dp[1]*1

class Solution:def numberOfArithmeticSlices(self, A):""":type A: List[int]:rtype: int"""n = len(A)if n < 3:return 0dp = [0] * n  #dp表初始为0sum = 0for i in range(2, n):  #从2开始if A[i]-A[i-1] == A[i-1]-A[i-2]:dp[i] = dp[i-1]+1sum += dp[i]return sum