Сумма подпоследовательности

Ответ 1

Создайте новый массив с каждым элементом, равным сумме предыдущих элементов плюс один.

Вход:

1  4 -3 -4  6  -7  8 -5

становится:

1  5  2  -2  4  -3  5  0
   ^                ^

Затем найдите элементы, которые совпадают в результирующем массиве.

Так как они представляют собой места, где общее изменение в функции равно нулю, вы обнаружите, что если их положение равно я и k, то подпоследовательность (i + 1, k) является подпоследовательностью с нулевой суммой. (В этом случае [2: 6]).

Кроме того, любые нули в таблице показывают, что подпоследовательность (0, k) является подпоследовательностью с нулевой суммой. Для поиска хеш-таблица или другой быстрый локатор столкновений делают это O (N) для выполнения.

Ответ 2

Сделайте текущую сумму, сохраняя значения суммы в хеш-таблице вместе с индексом массива

Если вы когда-либо получаете значение суммы, которое вы уже видели, верните 1 + индекс в хэш-таблице и текущий индекс. Это решение - сложность O (n) времени.

Нет необходимости в новом массиве. Сложность пространства - O (N) из-за хеша.

Реализация Python:

input = [1, 4, -3, -4, 6, -7, 8, -5]
map = {}
sum = 0
for i in range(len(input)):
    sum += input[i]
    if sum in map:
        print map[sum][0] + 1, "to", i
    map[sum] = (i, sum)

Обратите внимание, что повторяющиеся подпоследовательности не показаны, например: Если (1 - 2) - подпоследовательность и (от 3 до 4), то от 1 до 4 не будет показано. Вы можете добиться такого поведения, сохранив списки в каждой позиции карты:

for x in map[sum]:
    print x[0]+1, "to", i
map[sum].append((i, sum))

Ответ 3

Ниже приведена java-реализация решения, предложенного @Fabricio

    public static int countAllSubSequenceForZeroSum(int[] array) {
    int count = 0;
    Map<Integer, Integer> encounteredSum = new HashMap<>();
    int prev = array[0];
    if(prev == 0) {
        count++;
        System.out.println("Found at index: "+0);
    }
    for (int i = 1; i < array.length; i++) {
        prev += array[i];
        if(encounteredSum.containsKey(prev)) {
            System.out.println("Found at index: "+i+ " start index: "+encounteredSum.get(prev));
            printSequenceForZeroSum(array, i);
            count++;
        } else {
            encounteredSum.put(prev, i);
        }
    }
    return count;
}

public static void printSequenceForZeroSum(int[] array, int endIndex) {
    int sum = array[endIndex];
    while(sum!=0) {
        System.out.print(array[endIndex]+ "  ");
        sum += array[--endIndex];
    }
    System.out.println(array[endIndex]);
}

Ответ 4

Реализация С++ с логикой, аналогичной ответу Fabricio.

pair<int, int> FindSubsequenceSum(const vector<int>& arr)      
{
  map<int, int> sumMap;
  map<int, int>::iterator it;
  int sum = 0;
  for (int i = 0; i < arr.size(); i++) 
  {
    sum += arr[i];
    it = sumMap.find(sum);
    if (it != sumMap.end()) 
    {
        return make_pair(it->second + 1, i);
    } else {
        sumMap.insert(make_pair(sum, i));
  }
}

int main()
{
  int arr[] = {1,4,-3,-4,6,-7,8,-5};
  vector<int> input(arr, arr + sizeof(arr) / sizeof(arr[0]));
  pair<int, int> result = FindSubsequenceSum(input);

  cout << "(" << result.first << "," << result.second << ")" << endl;

  return 0;
}

Output:
(2,6)