Created
April 24, 2018 04:24
-
-
Save jianminchen/eec1916279c137f18f7d409a986677c1 to your computer and use it in GitHub Desktop.
Find subarray length with target elements and order doesn't matter, target can have duplicates
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
9:00pm | |
brute force | |
target [1,2,2,3] | |
arr[1,1,1,2,2,2,3,1,2,3] | |
find subarray length with all target elements and order doesn't matter, target can have duplicates, | |
3,2,2,1 | |
go through -> start position | |
1 1 | |
2 2 | |
3 1 | |
Find small smll | |
*/ | |
public static int FindShortestSubArrayLengthContainingAllKeys(int[] numbers, int[] target) | |
{ | |
if(numbers == null || target == null || numbers.Length < target.Length) | |
return -1; | |
var sLength = numbers.Length; | |
var tLength = target.Length; | |
var dict = new Dictionary<int, int>(); | |
foreach(var item in target) | |
{ | |
if(dict.ContainsKey(item)) | |
dict[item]++; | |
else | |
dict.Add(item, 1); | |
} | |
int minLength = Int.MaxValue; | |
int numbersFound = 0; | |
int start = 0; | |
for(int index = 0; index < numbers; index++) | |
{ | |
var current = numbers[index]; | |
if(dict.ContainsKey(current)) | |
continue; | |
if(dict[current] > 0) | |
{ | |
numbersFound++; | |
} | |
dict[current]--; | |
// slide left pointer | |
while(numbersFound == tLength) | |
{ | |
// record the length | |
var currentLength = index - start + 1; | |
minLength = currentLength < minLength ? currentLength : minLength; | |
// skip left if it is ok | |
var leftValue = numbers[start]; | |
if(dict.ContainsKey(leftValue)) | |
{ | |
if(dict[leftValue] >=0) | |
numbersFound--; | |
dict[leftValue]++; | |
} | |
start++; | |
} | |
} | |
// return minimum length | |
return minLength == int.MaxValue? -1 : minLength; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment