Leetcode 446. Арифметические фрагменты II - подпоследовательность - PullRequest
Новая
       65

Leetcode 446. Арифметические фрагменты II - подпоследовательность

0 голосов
/ 02 декабря 2018

Это вопрос к leetcode.Я использовал рекурсивную стратегию, но превышен лимит времени.Так может кто-нибудь дать мне несколько советов по улучшению моего алгоритма?Большое спасибо.

Это ссылка на вопрос: https://leetcode.com/problems/arithmetic-slices-ii-subsequence/description/

Есть мои оригинальные коды: 

class Solution:
def numberOfArithmeticSlices(self, A):
    """
    :type A: List[int]
    :rtype: int
    """
    A = sorted(A) 
    self.n = 0
    for x in range(len(A)):
        for y in range(x+1, len(A)):
            if A[-1] - A[y] < A[y] - A[x]: 
                break
            self.helper(y+1, A[y]-A[x], A, A[y])
    return self.n

# i represents the next index we should step through from, k represents 
# the current difference, prev represents the previous element so we 
# could calculate the current difference    

def helper(self, i, k, A, prev):   
    if i == len(A):
        return 
    for x in range(i, len(A)):
        if A[x] - prev == k:
            self.n += 1
            self.helper(x+1, k, A, A[x])
        elif A[x] - prev > k:
            return
...