Вчера был мой 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; } }