專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

之前有一位網(wǎng)友說找到了工作，學(xué)校不讓去實習(xí)，可以看下，我本來以為偷偷跑出去會沒事的，結(jié)果另一位網(wǎng)友因為偷偷跑出去實習(xí)40天，被導(dǎo)員發(fā)現(xiàn)了，要求第二天必須回去，不回去就開除，連離職的時間都不給?，F(xiàn)在大學(xué)都這樣嗎，為啥不允許學(xué)生實習(xí)。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第413題：等差數(shù)列劃分。

問題描述

來源：LeetCode第413題

難度：中等

如果一個數(shù)列至少有三個元素 ，并且任意兩個相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數(shù)列。

給你一個整數(shù)數(shù)組 nums ，返回數(shù)組 nums 中所有為等差數(shù)組的子數(shù)組個數(shù)。子數(shù)組是數(shù)組中的一個連續(xù)序列。

示例1：

輸入：nums = [1,2,3,4] 輸出：3 解釋：nums 中有三個子等差數(shù)組：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例2：

輸入：nums = [1] 輸出：0

• 1 <= nums.length <= 5000

• -1000 <= nums[i] <= 1000

問題分析

按照題的要求當(dāng)數(shù)組的長度小于3的時候是不能構(gòu)成等差數(shù)列的。 如果數(shù)組長度小于3，我們直接返回0。

定義一維數(shù)組dp，其中dp[i]表示以nums[i]為等差數(shù)列最后一個元素的等差數(shù)列個數(shù)。很明顯如果nums[i]可以和前面的數(shù)字可以構(gòu)成等差數(shù)列，那么dp[i]=dp[i-1]+1，如下圖所示

如果nums[i]和前面的數(shù)字不能構(gòu)成等差數(shù)列，那么dp[i]肯定是等于0的，我們還需要重新計算新的等差值diff。統(tǒng)計的時候只需要把所有等差數(shù)列的個數(shù)相加即可。

JAVA：

public int numberOfArithmeticSlices(int[] nums) {
    int len = nums.length;
    if (len < 3)// 如果構(gòu)不成等差數(shù)列，返回0
        return 0;
    int[] dp = new int[len];
    int count = 0;// 等差數(shù)列的個數(shù)
    // 等差數(shù)列的差值
    int diff = nums[1] - nums[0];
    for (int i = 2; i < len; i++) {
        if (nums[i] - nums[i - 1] == diff) {
            // 如果當(dāng)前數(shù)字和前面的可以構(gòu)成等差數(shù)列，
            // 就更新dp和count的值
            dp[i] = dp[i - 1] + 1;
            count += dp[i];
        } else {
            // 如果不能和前面的構(gòu)成等差數(shù)列，要重新計算diff
            diff = nums[i] - nums[i - 1];
        }
    }
    return count;
}

C++：

public:
    int numberOfArithmeticSlices(vector

  &nums) {         int len = nums.size();         if (len < 3)// 如果構(gòu)不成等差數(shù)列，返回0             return 0;         vector

  dp(len, 0);         int count = 0;// 等差數(shù)列的個數(shù)         // 等差數(shù)列的差值         int diff = nums[1] - nums[0];         for (int i = 2; i < len; i++) {             if (nums[i] - nums[i - 1] == diff) {                 // 如果當(dāng)前數(shù)字和前面的可以構(gòu)成等差數(shù)列，                 // 就更新dp和count的值                 dp[i] = dp[i - 1] + 1;                 count += dp[i];             } else {                 // 如果不能和前面的構(gòu)成等差數(shù)列，要重新計算diff                 diff = nums[i] - nums[i - 1];             }         }         return count;     }

Python：

def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    length = len(nums)
    if length < 3:  # 如果構(gòu)不成等差數(shù)列，返回0
        return 0
    dp = [0] * length
    count = 0  # 等差數(shù)列的個數(shù)
    diff = nums[1] - nums[0]  # 等差數(shù)列的差值
    for i in range(2, length):
        if nums[i] - nums[i - 1] == diff:
            # 如果當(dāng)前數(shù)字和前面的可以構(gòu)成等差數(shù)列，
            # 就更新dp和count的值
            dp[i] = dp[i - 1] + 1
            count += dp[i]
        else:
            # 如果不能和前面的構(gòu)成等差數(shù)列，要重新計算diff
            diff = nums[i] - nums[i - 1]
    return count

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。