(一)O(logN)的解法
首先將原數組處理成前項和的形式,這樣就保證了數組的有序(注意第一個是0,自己push進去),然後遍歷數組,尋找小於等於sum[i]+s的最小的下標,如果找不到,那麼break結束。否則繼續下去,最後取最小值。
class Solution { public: int minSubArrayLen(int s, vector& nums) { vector sum; int ans=100000000,temp=0; sum.push_back(0); for(int i=0;i (二) O(N)的解法
兩個指針, start end, end向後走,直到 sum 大於 s. 然後start向後, 直到sum 小於s. 同時更新 min值。類似於滑動窗口的形式。
public class Solution { //1,1,4 public int minSubArrayLen(int s, int[] nums) { //init check int start = 0; int end = 0; int sum = 0; int min = Integer.MAX_VALUE; while(start=s && start<=end) { min = Math.min(min, end-start); sum -= nums[start++]; } } return min==Integer.MAX_VALUE ? 0 : min; } }