Advertisement
kosievdmerwe

Sanitized Submission

Sep 10th, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.79 KB | None | 0 0
  1. class DPState:
  2.     def __init__(self):
  3.         # number which end at this
  4.         self.num_two_length = 0
  5.         self.num_arithmetic = 0
  6.  
  7. class Solution:
  8.     def numberOfArithmeticSlices(self, nums: List[int]) -> int:
  9.         N = len(nums)
  10.         dp = [defaultdict(DPState) for _ in range(N)]
  11.        
  12.         ans = 0
  13.         for i in range(N):
  14.             for j in range(i + 1, N):
  15.                 delta = nums[j] - nums[i]
  16.                
  17.                 dp[j][delta].num_two_length += 1
  18.                 if delta not in dp[i]:
  19.                     continue
  20.                    
  21.                 to_add = dp[i][delta].num_two_length + dp[i][delta].num_arithmetic
  22.                 dp[j][delta].num_arithmetic += to_add
  23.                 ans += to_add
  24.            
  25.         return ans
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement