Проверить, существуют ли в массиве 4 индекса, удовлетворяющих заданному условию

Опубликовано: 25 Февраля, 2023

Учитывая массив A[] из N положительных целых чисел и 3 целых чисел X, Y и Z, задача состоит в том, чтобы проверить, существуют ли 4 индекса (скажем, p, q, r, s), для которых выполняются следующие условия:

  • 0 < p < q < r < s < N
  • Сумма подмассива от A[p] до A[q – 1] равна X
  • Сумма подмассива от A[q] до A[r – 1] равна Y
  • Сумма подмассива от A[r] до A[s – 1] равна Z

Примеры:

Input: N = 10, A[] = {1, 3, 2, 2, 2, 3, 1, 4, 3, 2}, X = 5, Y = 7, Z = 5
Output: YES
Explanation: The 4 integers p, q, r, s are {1, 3, 6, 8}. 

  • A[1] + A[2] = 5
  • A[3] + A [4] + A[5] = 7
  • A[6] + A[7] = 5

Input:  N = 9, A[] = {31, 41, 59, 26, 53, 58, 97, 93, 23}, X = 100, Y = 101, Z = 100
Output: NO

Подход: Проблема может быть легко решена с помощью накопительной суммы и двоичного поиска.

If we calculate the cumulative sum of the array, then the sum of any subarray can be computed in O(1). Say S[i] is cumulative sum till ith index, then S[j] – S[i] = A[i] + A[i + 1] + …. + A[j – 1].

So, given conditions can be converted into the following:

We need to find 4 integers p, q, r, s such that: 

S[q] – S[p] = X
S[r] – S[q] = Y
S[s] – S[r] = Z

Now, for any fixed index (say p), we can find another index (say q) using binary search in a monotonically increasing array (cumulative sum), such that S[q] = S[p] + X. Similarly, we can find r and s. We can perform this search for all possible indices.

NOTE: A set can be used so that we won’t need to perform a binary search explicitly each time.

Таким образом, проблема может быть решена с помощью следующих шагов:

  • Объявите набор (скажем, S).
  • Инициализируйте переменную (скажем, curr) 0, чтобы вычислить кумулятивную сумму на каждой итерации.
  • Перебрать заданный массив и вставить совокупную сумму в набор.
  • Перебрать набор и проверить, удовлетворяет ли текущий элемент набора заданному условию вместе с тремя другими элементами (которые также входят в набор). Если это так, верните true.
  • В противном случае верните ложь.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * log(N))
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ