leetcode-413. 等差數列劃分

難度 - 中等
原題鏈接 - 等差數列劃分

題目描述

如果一個數列 至少有三個元素 ，并且任意兩個相鄰元素之差相同，則稱該數列為等差數列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數列。
給你一個整數數組 nums ，返回數組 nums 中所有為等差數組的 子數組 個數。
子數組 是數組中的一個連續序列。

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

示例 2：
輸入：nums = [1]
輸出：0

提示：
1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000

雙指針

這道題，我們先求出有連續符合要求的子序列的個數。
可以用雙指針，一個卡住左指針，一個指針向右滑動，然后用等差數列求和公式求出個數就行了。

具體的，我們可以枚舉 i 作為差值為 d 的子數組的左端點，然后通過「雙指針」的方式找到當前等差并最長的子數組的右端點 j，令區間 [i,j]長度為 len。
那么顯然，符合條件的子數組的數量為：
cnt=∑k=3lencountWithArrayLength(k)

函數 int countWithArrayLength(int k) 求的是長度為 k 的子數組的數量。
不難發現，隨著入參 k 的逐步減小，函數返回值逐步增大。
因此上述結果 cnt其實是一個 首項為 1，末項為 len?3+1，公差為 1 的等差數列的求和結果。直接套用「等差數列求和」公式求解即可。

代碼

  /*** 等差數列的個數* @param nums* @return*/public int numberOfArithmeticSlices(int[] nums) {//保存答案int ans = 0;if (nums.length < 3){return ans;}for (int i = 0; i < nums.length - 2;){int j = i;//等差int dn = nums[j + 1] - nums[j];//找到滿足等差數列的右邊界while (j + 1 < nums.length && dn == (nums[j + 1] - nums[j])){j++;}//子數組的長度int ln = j - i + 1;//最短長度是3 計算子數組個數int an = ln - 3 + 1;//等差數列個數  求和公式int cnt = (1 + an) * an / 2;ans += cnt;i = j;}return ans;}

上期經典算法

leetcode611. 有效三角形的個數