微软 20220826 笔试第三题
Leetcode Link: 413. 等差数列划分 - 力扣（LeetCode）
题目
解法一：贪心+差分数组
思路： 关注到本题只是关注子数组，并不是子序列，会更简单。
只需要先遍历求一次差分（差分数组的长度比原来的数组的长度小 1）
nums = [1,3,5,8,1, 5,6]
diff = [ 2,2,3,-7,4,1 ]即 diff[i] 表示 nums[i+1]-nums[i] 的值
接下来我们直接遍历 diff，固定左指针，增加右指针，逐个找到相邻值相等的最长子序列，这样我们就等价于找到了以左指针为起点的最长的等差数列，那么这个等差数列中有元素 right-left+2 个（结合例子）
对于一个等差数列[1, 2, 3, 4, 5]，其能够贡献的等差数列 (子数组) 为
含有 5 个元素 → 1
含有 4 个元素 → 2
含有 3 个元素 → 3
可以看到，相当于一个长度为对应元素的窗能够平移的次数。
我们知道一个等差数列的长度为 n=right-left+2，此时能够贡献的满足题意的子数组总数为 1+2+3+…+n-2 = (n-1)*(n-2)/2
最后是n-2是因为子数组的最小长度为3
题解：
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
# 求差分数组
diff = [0 for _ in range(len(nums)-1)]
for i in range(len(nums)-1):
diff[i] = nums[i+1] - nums[i]
# 遍历找每一个最长的等差数列
left = right = 0
res = 0
while(right<len(diff) and left<len(diff)):
while(right+1<len(diff) and diff[right+1] == diff[right]):
right += 1
n = right-left+2 # 等差数列的长度
if n>=3:
res += (n-1)*(n-2) // 2
left = right
else:
left += 1
right += 1
return res解法二
思路：
题解：
解法三
思路：
题解：