Minimum Size Subarray containing Subsequence


  • 0

    Given an array nums and a subsequence sub, find the shortest subarray of nums that contains sub.

    Example: nums = [1,2,3,5,8,7,6,9,5,7,3,0,5,2,3,4,4,7], sub = [5,7]
    Answer: start = 8, size = 2

    If such subarray does not exist, return -1, -1.
    Note that the subarray must contain the elements of sub in the correct order..


  • 0
    R

    @agave The order of sub that needs to be present in the nums should be in the same sequence?


  • 0
    public static string FindShortestSubArray(int[] nums, int[] sub)
    		{
    			int j = 0;
    			int Index = -1; int minIndex = -1;
    			int size = 0; int minSize = -1;
    			 
    			bool countSize = false;
    
    
    			for (int i = 0; i < nums.Length; i++)
    			{
    				if (sub[j] == nums[i])
    				{
    					if (j == 0) { Index = i; }
    
    					j++; countSize = true;
    				}
    				else
    				{
    					if (nums[i] == sub[0] && j == 1) { Index = i; j = 0; size = 0; j++; countSize = true; }
    				}
    
    
    				if (countSize == true)
    				{
    					size++;
    				}
    
    				if (j == sub.Length)
    				{
    					if ((minSize > size) || (minSize == -1 && minIndex == -1))
    					{
    						minIndex = Index;
    						minSize = size;
    					}
    
    					j = 0; size = 0; countSize = false;
    				}
    			}
    
    
    			return minIndex.ToString() + ' ' + minSize.ToString();
    		}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.