LeetCode -- Minimum Size Subarray Sum

LeetCode -- Minimum Size Subarray Sum

題目描述：


Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.


For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.


對於數組A中的子數組a，找到滿足Sum(a[0]+a[1]...a[n-1]) >= target時的最短長度的子數組。


思路：
本題屬於移動窗口問題，最直接的辦法就是分別以a[i]為起點，不斷往後移動指針進行累加存到s，當s>=target時，更新最短長度min。
時間復雜度為O(N^2)

實現代碼：

 

public class Solution {
    public int MinSubArrayLen(int s, int[] nums) 
    {
       	int? min = null;
    	
    	for(var i = 0;i < nums.Length; i++){
    		var l = MinLen(nums, i, s);
    		if(l.HasValue && l < min || min == null){
    			min = l;
    		}
    	}
    	
    	return min.HasValue ? min.Value : 0;
    }
    
    private int? MinLen(int[] nums, int start, int target)
    {
    	var s = 0;
    	var startFrom = start;
    	while(start < nums.Length){
    		s += nums[start];
    		if(s >= target){
    			return (start - startFrom + 1);
    		}
    		start ++;
    	}
    	
    	return null;
    }
    
}

本題使用two pointer可以完成o(N)的實現。 比較推薦這種實現方式。


1. 使用left和right兩個指針分別從0作為起點
2. 如果當前s小於target，right一直往後走，直到s大於或等於target
3. 如果s大於等於target，left一直往後走，同時判斷left與right的距離，更新最小窗口的大小。


本實現方式參考了連接：
http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/




實現代碼：

 

 

public class Solution {
    public int MinSubArrayLen(int s, int[] nums) 
    {
       	var len = nums.Length;
    	var sum = 0;
    	int? min = null;
    	
     	// use two pointers 
        var start = 0;
    	var end = 0;
    	
        while (end < len)
        {
    		// if current sum if smaller , keep moving right pointer forward
            while (sum < s && end < len){
                sum += nums[end];
    			end ++;
    		}
     		
    		// if sum is more than target, keep moving left pointer forward to shrink the window size
            while (sum >= s)
            {
    			// find a smaller window then update size
                if (!min.HasValue || end - start < min){
    				min = end - start;
    			}
    			
    			// unload left most value from sum
                sum -= nums[start];
    			start ++;
            }
    		
    		// now sum less than target again
    		// lets play again with the right pointer if not yet reach the end
        }
    	
        return !min.HasValue ? 0 : min.Value;
    }
    
    
}