Поиск минимальной длины подмассива

Дана последовательность положительных целых чисел и число S. Найдите минимальную длину подмассива, сумма элементов которого будет больше или равна S. Если такой подмассив не существует, верните 0.

Примеры:

  1. Вход: nums = [2,3,1,2,4,3], S = 7
    Выход: 2
    Объяснение: Самый короткий подмассив, сумма которого ≥ 7, это [4,3] и его длина равна 2.
  2. Вход: nums = [1,4,4], S = 4
    Выход: 1
    Объяснение: Самый короткий подмассив, сумма которого ≥ 4, это [4] и его длина равна 1.
  3. Вход: nums = [1,1,1,1,1,1,1,1], S = 11
    Выход: 0
    Объяснение: Ни один подмассив не имеет сумму, большую или равную 11.
@RunWith(RobolectricTestRunner::class)  
class MinSubArrayLen {  
    @Test  
    fun makeTest() {  
        Assert.assertEquals(2, minSubArrayLen(7, intArrayOf(2, 3, 1, 2, 4, 3)))  
        Assert.assertEquals(5, minSubArrayLen(15, intArrayOf(1, 2, 3, 4, 5)))  
        Assert.assertEquals(3, minSubArrayLen(11, intArrayOf(1, 2, 3, 4, 5)))  
    }  
}

fun minSubArrayLen(s: Int, nums: IntArray): Int {
    var left = 0
    var sum = 0
    var minLength = Int.MAX_VALUE

    for (right in nums.indices) {
        sum += nums[right]

        while (sum >= s) {
            minLength = minOf(minLength, right - left + 1)
            sum -= nums[left]
            left++
        }
    }

    return if (minLength == Int.MAX_VALUE) 0 else minLength
}

Объяснение:

  1. Инициализируем два указателя: left и right. Указатель right используется для расширения окна подмассива, а left - для его сужения.
  2. Проходим по массиву с помощью указателя right, добавляя текущий элемент к сумме sum.
  3. Когда сумма sum становится больше или равной s, обновляем минимальную длину подмассива minLength и затем уменьшаем сумму, сдвигая указатель left вправо.
  4. Продолжаем уменьшать размер окна, пока сумма sum остается больше или равной s.
  5. Если минимальная длина minLength осталась неизменной, возвращаем 0, иначе возвращаем minLength.

Этот метод эффективно находит минимальный подмассив с суммой, не менее s, с помощью одного прохода по массиву.

Альтернативное неоптимальное решени

fun minSubArrayLen(s: Int, nums: IntArray): Int {  
    if (nums.isEmpty()) return 0  
    var result = Integer.MAX_VALUE  
  
    for (left in nums.indices) {  
        var sum = 0  
        for (right in left until nums.size) {  
            sum += nums[right]  
  
            if (sum >= s) {  
                val currentLen = 1 + right - left  
                if (currentLen < result)  
                    result = currentLen  
                break  
            }  
        }  
    }  
  
    return result  
}

Ваше решение правильно определяет минимальную длину подмассива, сумма которого равна или превышает SSS, но оно может быть оптимизировано. Текущий алгоритм работает за O(n2)O(n^2)O(n2) из-за вложенных циклов, что может быть неэффективно при больших размерах массива.

Оптимизация возможна с использованием метода двух указателей (или "скользящего окна"), что позволит сократить время выполнения до O(n)O(n)O(n). Вот как можно переписать решение:

Как работает оптимизированное решение:

  1. Использование двух указателей:
    • right двигается по массиву, добавляя элементы к текущей сумме.
    • left двигается, когда текущая сумма становится больше или равна SSS, тем самым уменьшая длину подмассива, если это возможно.
  2. Обновление минимальной длины:
    • Как только сумма становится больше или равна SSS, мы обновляем минимальную длину и пытаемся сдвинуть левый указатель (left), чтобы найти более короткий подмассив с суммой ≥S\geq S≥S.
  3. Результат:
    • Если минимальная длина была обновлена, она возвращается. Если нет, значит, подходящий подмассив не найден, и возвращается 0.

Основные отличия:

  1. Эффективность вашего решения:
    В вашем коде вложенный цикл заставляет каждый раз начинать суммирование элементов от left до right. В худшем случае (например, когда подходящий подмассив находится в конце), это приводит к тому, что сумма каждого подмассива вычисляется несколько раз, что приводит к квадратичной временной сложности O(n2)O(n^2)O(n2).
  2. Эффективность предложенного решения:
    В предложенном решении цикл идет один раз по массиву, и мы используем скользящее окно: при добавлении элемента к сумме мы пытаемся минимизировать размер окна, сдвигая left. Таким образом, сумма элементов пересчитывается один раз за проход, что снижает временную сложность до O(n)O(n)O(n).

Пример работы:

Рассмотрим массив nums = [2,3,1,2,4,3] и S=7S = 7S=7.

  • Ваш алгоритм:
    • left = 0, идет расчет сумм: [2], [2,3], [2,3,1], [2,3,1,2], [2,3,1,2,4] (наконец, >= 7). right = 4, длина = 5.
    • Затем left = 1, [3], [3,1], [3,1,2], [3,1,2,4] (>= 7). right = 4, длина = 4.
    • И так далее до нахождения минимальной длины подмассива.
  • Оптимизированный алгоритм:
    • right = 0, добавляем 2 к сумме.
    • right = 1, добавляем 3 (сумма 5), двигаемся дальше.
    • right = 2, добавляем 1 (сумма 6), двигаемся дальше.
    • right = 3, добавляем 2 (сумма 8, >= 7). Вычисляем длину подмассива right - left + 1 = 4, затем уменьшаем окно (вычитаем 2 из суммы, left = 1, сумма 6).
    • right = 4, добавляем 4 (сумма 10, >= 7). Длина = 3, сдвигаем left.
    • И так далее.

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