假设我们需要编写一个函数,该函数将一个数组作为输入并返回包含不超过两个不同数字的数组的最大切片。如果我们仔细研究这个问题,这将涉及检查稳定的子数组并遍历原始数组。
因此,滑动窗口算法非常适合于此。通过滑动窗口算法解决此问题的代码将是-
const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1 ,1 ,1, 8, 1, 1, 8, 8]; const map = { length: 0 }; let required = []; for(start = 0, end = 0; end <= arr.length; ){ if(map.length > 2){ if(map[arr[start]] === 1){ delete map[arr[start]]; map.length --; }else{ map[arr[start]]--; }; start++; }else{ if(end - start > required.length){ required = arr.slice(start, end); }; if(map[arr[end]]){ map[arr[end]]++; }else{ map[arr[end]] = 1; map.length++; } end++; } } console.log(required);
我们维护了一个用于存储数组中任意点的不同字符数的映射,并不断比较每次迭代中最长子数组的长度,当不同字符数超过2时,我们向右滑动数组以寻找下一个稳定点数组。
输出结果
控制台中的输出将为-
[ 1, 8, 1, 1, 1, 1, 8, 1, 1, 8, 8 ]