SHEIN 后台开发工程师笔试
刷题刷得我迷迷糊糊的 题目 一个target字符串 一个字符数组 nums 找出nums中包含target 的最小连续子数组 输入 target = abc, nums = [c,a,c,b,c,c] 输出 [1,4]
可能是将最长公共子序列改的
String target = "abc";
char[] nums = {'c','a','c','b','c','c'};
char[] targets = target.toCharArray();
int[][]dp = new int[targets.length+1][nums.length+1];
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int i = 0; i < targets.length; i++){
for(int j = 0; j < nums.length; ++j){
if(targets[i] == nums[j]) {
dp[i+1][j+1] = dp[i][j]+1;
if(i == targets.length-1 && dp[i+1][j+1] == targets.length){
minHeap.offer(j);
}
}else{
dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]);
}
}
}
if(!minHeap.isEmpty()){
System.out.println(minHeap.poll());
} else
System.out.println("null");
类似资料：