Найдите длину наибольшего подмассива с суммой 0 - PullRequest
Новая
       22

Найдите длину наибольшего подмассива с суммой 0

0 голосов
/ 01 августа 2020

Учитывая массив целых чисел, найдите длину самого длинного подмассива с суммой, равной 0. 

Examples :

Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23};
Output: 5
Explanation: The longest sub-array with 
elements summing up-to 0 is {-2, 2, -8, 1, 7}

Input: arr[] = {1, 2, 3}
Output: 0
Explanation:There is no subarray with 0 sum

Вот подход к этой проблеме

Эффективный подход 

hash_map = {} 
  
    max_len = 0
  
    curr_sum = 0
  
    for i in range(len(arr)): 
        curr_sum += arr[i] 
  
        if arr[i] is 0 and max_len is 0: 
            max_len = 1
  
        if curr_sum is 0: 
            max_len = i + 1
        if curr_sum in hash_map: 
            max_len = max(max_len, i - hash_map[curr_sum] ) 
        else: 
  
            # else put this sum in dictionary 
            hash_map[curr_sum] = i 
  
    return max_len

Но не работает для таких тестовых случаев, как, 

[8, -8, 7, -7, 15, -15] OR
[10, -10, 12, -12, 13, -13]

Есть ли у вас другой подход к этой проблеме?

1 Ответ

0 голосов
/ 01 августа 2020

Разобрать решение из комментария. Сначала создайте генератор для получения всех подмассивов: 

def gen_subarrays(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)+1):
            yield arr[i:j]

, затем функцию для получения всех массивов с нулевой суммой: 

def find_zero_sums(sarrays):
    for sa in sarrays:
        if sum(sa) == 0:
            yield sa

, а затем функцию для отслеживания самый длинный: 

def longest_zero_sum(arr):
    longest = []
    for zs in find_zero_sums(gen_subarrays(arr)):
        if len(zs) > len(longest):
            longest = zs
    return longest

вывод: 

print(longest_zero_sum([15, -2, 2, -8, 1, 7, 10, 23]))
print(longest_zero_sum([1,2,3]))
print(longest_zero_sum([8, -8, 7, -7, 15, -15]))
print(longest_zero_sum([10, -10, 12, -12, 13, -13]))
print(longest_zero_sum([1,3,0,4,5]))

is 

[-2, 2, -8, 1, 7]
[]
[8, -8, 7, -7, 15, -15]
[10, -10, 12, -12, 13, -13]
[0]

Вы можете получить более эффективное решение, если отсортируете индексы подмассива по убыванию длины . Тогда первый подмассив, который вы обнаружите, что сумма к нулю является самым длинным: 

def gen_subarrays(arr):
    indices = [(i,j) for i in range(len(arr)) for j in range(i+1, len(arr)+1)]
    indices.sort(key=lambda (i,j): i-j)  # sort on length (-(j-i))
    for i, j in indices:
        yield arr[i:j]

def longest_zero_sum(arr):
    for sa in gen_subarrays(arr):
        if sum(sa) == 0:
            return sa
    return []

результат такой же, как и выше.

...