Descubrí cómo hacer esto usando dos bucles, pero me pregunto si hay una mejor manera de abordar esta pregunta de subarreglo contiguo. Mi corazonada es usar el patrón de ventana deslizante, pero he estado luchando con la configuración y si puedes resolver esto en una sola pasada. Si alguien pudiera ayudar con una pseudocodificación clara o en Javascript, se lo agradecería.
You are given an array of integers numbers and an integer k. Your task is to count the number of contiguous subarrays containing at least k numbers which appear exactly once in this subarray. Example For numbers = [1, 2, 1, 1] and k = 2, the output should be uniquesOnSegment(numbers, k) = 2. There are 2 subarrays satistfying the criteria of containing at least k = 2 numbers exactly once: numbers[0..1] = [1, 2] numbers[1..2] = [2, 1] Note that the subarray numbers[0..2] = [1, 2, 1] is not counted because the number 1 appears twice, so only one number appears exactly once in this subarray. For numbers = [1, 2, 3, 4, 1] and k = 3, the output should be uniquesOnSegment(numbers, k) = 6. There are 6 subarrays that satisfy the criteria of containing at least k = 3 numbers occuring exactly once: numbers[0..2] = [1, 2, 3] numbers[0..3] = [1, 2, 3, 4] numbers[0..4] = [1, 2, 3, 4, 1] numbers[1..3] = [2, 3, 4] numbers[1..4] = [2, 3, 4, 1] numbers[2..4] = [3, 4, 1] For numbers = [5, 5, 5, 5] and k = 2, the output should be uniquesOnSegment(numbers, k) = 0. There are no subarrays with at least k = 2 different numbers. For numbers = [5, 5, 5, 5] and k = 1, the output should be uniquesOnSegment(numbers, k) = 4. There are 4 subarrays that satisfy the criteria of containing at least k = 1 occuring exactly once: numbers[0..0] = [5] numbers[1..1] = [5] numbers[2..2] = [5] numbers[3..3] = [5]Solución de dos bucles (¿hay una forma más óptima?):
function uniquesOnSegment(arr, k) { let countUniqueSubarrays = 0; for (let i = 0; i < arr.length; i++) { let windowSubarray = new Set(); let subarray = []; let nonUniques = 0; for (let j = i; j < arr.length; j++) { const currentNum = arr[j]; subarray.push(currentNum); if (windowSubarray.has(currentNum)) { nonUniques++; } else { windowSubarray.add(currentNum); } if (windowSubarray.size - nonUniques >= k) { countUniqueSubarrays++; } } } return countUniqueSubarrays; } console.log(uniquesOnSegment([1, 2, 3, 4, 1], 3)); // 6 console.log(uniquesOnSegment([1, 2, 1, 1], 2)); // 2Aquí podría hacerlo en 2 bucles anidados (contando la búsqueda de max en Object.values). Creo que se puede mejorar aún más, pero esto es lo que se me ocurrió hasta ahora.
const numbers = [5,5,5,5] const k = 1 const numbers1 = [1, 2, 3, 4, 1] const k1 = 2 const numbers2 = [1, 2, 2, 4, 1] const k2 = 3 var countSubArray = function(arr, k) { let base = {} let count = 1; //We are hoping the next contiguous subarray will have all uniques for ( let i = 0; i < k; i++ ) { if(base[arr[i]] === undefined) base[arr[i]] = 0 else count -= 1 base[arr[i]] += 1 } // Now sliding window starting at i = 1 for ( let i = 1; i < arr.length - k + 1; i++ ) { count += 1; if ( base[arr[i - 1]] > 0 ){ base[arr[i - 1] ] -= 1 if ( base[arr[i - 1]] > 1 ){ count -= 1 } else { delete base[arr[i - 1]] if (base[arr[i + k]] === undefined ) { base[arr[i + k]] = 1 } else { count -= 1 } if ( Math.max(...Object.values(base)) > 1 ) { count -= 1 } } } } return count } console.log(countSubArray(numbers, k)) console.log(countSubArray(numbers1, k1)) console.log(countSubArray(numbers2, k2))