用Python编写程序检查查询找到的有效算术序列的数量

假设我们有一个名为nums的数字列表并且还有一个查询列表。每个查询元素都包含[i，j]。因此，此查询询问是否[nums中的子列表，范围在[i，j]（包括两个范围）之间]是等差数列。因此，最后我们必须找到返回true的查询计数。

因此，如果输入如下nums = [2, 4, 6, 8, 7, 6, 5, 2]，queries = [[3, 4]，[0, 3]，[2, 4]]，则输出将是2，因为[2，4，6，8]是一个等差数列，所以查询[0，3]是真的。对于[8，7]也是等差数列，所以查询[3，4]也是真的。但是[6，8，7]不是等差数列，所以[2，4]不正确。

为了解决这个问题，我们将遵循以下步骤−

• 如果nums为空，则
  • 返回0
• n：nums的大小
• diff：一个具有元素（nums [i + 1] – nums [i]）的列表，对于每个i在0到n-2的范围内
• rle：大小为（n-1）的列表，并填充为0
• 对于范围从0到n-2的i，执行
  • 如果i > 0并且diff [i]与diff [i-1]相同，则
    • rle [i]：= rle [i-1] + 1
  • 否则，
    • rle [i]：= 1
• ans：= 0
• 对于查询中的每个（i，j），执行
  • 如果i与j相同，则
    • ans：= ans + 1
  • 否则，
    • ans：= ans +（1如果rle [j-1]≥（j-i），否则0）
• 返回ans

例子

让我们看一下以下实现以更好地理解−

def solve(nums, queries):
   if not nums:
      return 0

   n = len(nums)
   diff = [nums[i + 1] - nums[i] for i in range(n - 1)]

   rle = [0] * (n - 1)
   for i in range(n - 1):
      if i > 0 and diff [i] == diff [i-1]:
         rle [i] = rle [i-1] + 1
      else:
         rle [i] = 1

   ans = 0
   for i，j in queries：
      如果i == j：
          ans + = 1
      否则：
          ans + = rle [j-1] ≥（j-i）
   return ans

nums = [2, 4, 6, 8, 7, 6, 5, 2]
queries = [[3, 4]，[0, 3]，[2, 4]]
print(solve(nums，queries))

输入

[2, 4, 6, 8, 7, 6, 5, 2]，[[3, 4]，[0, 3]，[2, 4]]

输出

2