Problem statement

https://binarysearch.com/problems/Arithmetic-Sequence-Queries/

Solution

For every index i find the longest arithmetic sequence which ends with this index. Then check each query in O(1).

Complexity

Time is O(n + q), space is O(n).

Code

class Solution:
    def solve(self, nums, Q):
        if not nums: return 0
        n, ans = len(nums), 0
        dp = [2] * n
        dp[0] = 1
        for i in range(2, n):
            if nums[i-1] - nums[i-2] == nums[i] - nums[i-1]:
                dp[i] = dp[i-1] + 1

        for x, y in Q:
            ans += dp[y] >= (y - x + 1)

        return ans