LeetCode刷题——等差数列划分#413#Medium

等差数列划分的思路探讨与源码
    等差数列划分的题目如下图，该题属于数组类和动态规划类型的题目，主要考察对于动态规划方法的使用和数组结构的理解。本文的题目作者想到2种方法，分别是滑动窗口方法和动态规划方法，其中滑动窗口方法使用Java进行编写，而动态规划方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用滑动窗口方法的思路进行解决，首先计算数组的长度，并校验长度是否比3小，如果是就返回0并结束。然后计算前两个元素的差值记录并初始化参数，开始循环遍历，从第三个元素开始，对每个元素都计算和前一个元素的差值并判断差值是否和之前的记录值是否相等，如果是就把下标值加1，否则就把返回值进行计算后重置下标值，直到遍历结束后，再次重新计算返回值，并且返回最终结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
public class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int numLen = nums.length;
        if (numLen < 3) {
            return 0;
        }
        int diffRes = nums[1] - nums[0];
        int L = 2;
        int res = 0;
        for (int ir = 2; ir < numLen; ir++) {
            int diff = nums[ir] - nums[ir - 1];
            if (diff == diffRes) {
                L = L + 1;
            } else {
                res = res + (L - 1) * (L - 2) / 2;
                L = 2;
                diffRes = diff;
            }
        }
        res = res + (L - 1) * (L - 2) / 2;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    显然，我们的滑动窗口方法的效果不错，还可以使用动态规划方法解决。首先计算数组长度并判断长度是否小于3，如果是就直接返回0并结束。初始化长度等于数组的动态规划数组，赋值全部为0，从第三个下标开始遍历循环，判断数组当前元素和前一个元素的差值是否和前一个元素与往前2个位置元素的差值相等，如果是就把动态规划数组的值进行迭代计算加1，判断前一个元素是否不为0，如果是就把当前元素和前一个元素的值叠加到当前元素上，直到遍历结束，计算动态规划数组各个元素的求和结果并返回。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        numLen = len(nums)
        if(numLen < 3):
            return 0
        dpArr = [0]*numLen
        for ir in range(2,numLen):
            if(nums[ir]-nums[ir-1]==nums[ir-1]-nums[ir-2]):
                dpArr[ir] = dpArr[ir] + 1
                if(dpArr[ir-1] != 0):
                    dpArr[ir]= dpArr[ir] + dpArr[ir-1]
        return sum(dpArr)
1
2
3
4
5
6
7
8
9
10
11
12
13

    从结果来说Java版本的滑动窗口方法的效率不错，而Python版本的动态规划方法的速度也很好，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。