Voltar
O que é Sliding Window?
Sliding Window
Sliding window é uma técnica utilizada para resolver problemas em que precisamos encontrar ou verificar um subarray que satisfaça uma determinada condição. Uma vez que a condição é atendida, retornamos os índices, um valor booleano ou algum outro resultado.
Eu realmente gosto deste problema (Contains Duplicate II🔗) e da ideia para resolvê-lo:
A ideia principal aqui é usar um hashmap desta maneira:
- A “Chave” do hashmap é o nosso valor/elemento no array
- O “Valor” da “Chave” do hashmap é o índice em que o elemento aparece
Com estes dois pontos em mente, temos tudo o que precisamos para resolvê-lo:
Iteramos pelo array de inteiros e verificamos:
- Se o elemento atual já existe em nosso hashmap, satisfazemos a condição
nums[i] == nums[j]
, porque se já existe, temos duas ocorrências do mesmo número - Se a diferença entre seus índices (j - i) é menor ou igual a K, retornamos verdadeiro
Usei Go para esta solução:
func containsNearbyDuplicate(nums []int, k int) bool {
// Cria o hashmap
h := make(map[int]int)
// Itera sobre o array
for index,element := range nums {
// Obtém o índice anterior no hashmap se o elemento existir
prevIndex, elementExists := h[element]
// Verifica se o elemento tem duas ocorrências (nums[i] == nums[j])
// e se a diferença de índices (index - prevIndex) é <= k
if elementExists && index - prevIndex <= k {
return true
}
// Se o elemento não existir, adicionamos ao hashmap
h[element] = index
}
return false
}
bool ContainsNearbyDuplicate(int[] nums, int k) {
Dictionary<int, int> dic = new Dictionary<int, int>();
var end = 0;
while (end < nums.Length) {
int element = nums[end];
if (dic.TryGetValue(element, out int value) && Math.Abs(end - value) <= k) {
return true;
}
dic[element] = end;
end++;
}
return false;
}
A ideia é a mesma para ambos os códigos acima.
Aqui está um esboço simples descrevendo a lógica que usei para resolver este problema (com go, mas a ideia é a mesma com C#)