Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class DPState:
- def __init__(self):
- # number which end at this
- self.num_two_length = 0
- self.num_arithmetic = 0
- class Solution:
- def numberOfArithmeticSlices(self, nums: List[int]) -> int:
- N = len(nums)
- dp = [defaultdict(DPState) for _ in range(N)]
- ans = 0
- for i in range(N):
- for j in range(i + 1, N):
- delta = nums[j] - nums[i]
- dp[j][delta].num_two_length += 1
- if delta not in dp[i]:
- continue
- to_add = dp[i][delta].num_two_length + dp[i][delta].num_arithmetic
- dp[j][delta].num_arithmetic += to_add
- ans += to_add
- return ans
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement