Вчера был мой 54-й день кодинга. вчера решил одну задачу

Проблема: Сумма подмассива минимального размера

Учитывая массив положительных целых чисел nums и положительное целое число target, вернуть минимальную длину элемента

подмассив

сумма которых больше или равна target. Если такого подмассива нет, вместо этого верните 0.

Пример 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Пример 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Пример 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Ограничения:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

Дальнейшие действия. Если вы нашли решение O(n), попробуйте написать другое решение, временная сложность которого равна O(n log(n)).

Решение (в Java):

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
  if(nums==null||nums.length==0)
        return 0;
 
    int i=0; 
    int j=0;
    int sum=0;
 
    int minLen = Integer.MAX_VALUE;
 
    while(j<nums.length){
        if(sum<target){
            sum += nums[j];
            j++;        
        }else{
            minLen = Math.min(minLen, j-i);
            if(i==j-1)
                return 1;
 
            sum -=nums[i];
            i++;
        }
    }
 
    while(sum>=target){
        minLen = Math.min(minLen, j-i);
 
        sum -=nums[i++];
    }
 
    return minLen==Integer.MAX_VALUE? 0: minLen;
    }
}