Под массив, который производит данную сумму и продукт

Question

Учитывая массив длины N. Как вы найдете минимальную длину смежное множество, сумма которого равна S, а произведение равно P. Например, 5 6 1 4 6 2 9 7 for S = 17, Ans = [6, 2, 9] for P = 24, Ans = [4 6].

Answer 1

Просто идите слева направо и сложите все числа, если сумма> S, затем отбросьте левые.

import java.util.Arrays;

public class test {
    public static void main (String[] args) {
        int[] array = {5, 6, 1, 4, 6, 2, 9, 7};
        int length = array.length;
        int S = 17;
        int sum = 0;                       // current sum of sub array, assume all positive
        int start = 0;                     // current start of sub array
        int minLength = array.length + 1;  // length of minimum sub array found
        int minStart = 0;                  // start of of minimum sub array found
        for (int index = 0; index < length; index++) {
          sum = sum + array[index];
          // Find by add to right
          if (sum == S && index - start + 1 < minLength) {
              minLength = index - start + 1;
              minStart = start;
          }
          while (sum >= S) {
            sum = sum - array[start];
            start++;
            // Find by minus from left
            if (sum == S && index - start + 1 < minLength) {
                minLength = index - start + 1;
                minStart = start;
            }
          }
        }
        // Found
        if (minLength != length + 1) {
            System.out.println(Arrays.toString(Arrays.copyOfRange(array, minStart, minStart + minLength)));
        }
    }
}

---

Для вашего примера, я думаю, что это ИЛИ .

Продукт ничем не отличается от сумма , кроме расчета.

Answer 2

Поместите два индекса в массив.Позволяет называть их я и J.Первоначально j = 1 и i = 0.Если произведение между i и j меньше P, увеличьте j.Если это больше, чем P, увеличить i.Если мы получим что-то равное p, суммируем элементы (вместо того, чтобы суммировать каждый раз, сохраняем массив, где S (i) - сумма всего слева от него. Вычисляем сумму от i до j как S (i) -S (j)) и посмотрите, получите ли вы S. Остановитесь, когда j выпадет из длины массива.

Это O (n).

Answer 3

псевдокод:

subStart = 0;
Sum = 0
for (i = 0; i< array.Length; i++)
    Sum = Sum + array[i];
    if (Sum < targetSum) continue;
    if (Sum == targetSum) result = min(result, i - subStart +1);
    while (Sum >= targetSum)
        Sum = Sum - array[subStart];
        subStart++;

Я думаю, что результат будет найден за один проход по массиву.В значении result отсутствует некоторая детализация.Требуется немного больше сложности, чтобы иметь возможность возвращать фактический подмассив при необходимости.

Чтобы найти подмассив Product, просто замените умножение / деление на сложение / вычитание в приведенном выше алгоритме

Answer 4

Вы можете использовать хэш-карту, чтобы найти ответ для продукта за O (N) время с дополнительным пробелом.