滑動(dòng)窗口秒存在重復(fù)元素 II
前言
大家好，我是熊哥，來(lái)自華為。今天給大家?guī)?lái)一道與滑動(dòng)窗口和查找表相關(guān)的題目，這道題同時(shí)也是 airbnb 和 Palantir 的面試題，即力扣上的第219題-存在重復(fù)元素 II。
本文主要介紹滑動(dòng)窗口加哈希表的策略來(lái)解答此題，供大家參考，希望對(duì)大家有所幫助。
存在重復(fù)元素 II
給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j，
使得 nums[i] = nums[j]，并且 i 和 j 的差的絕對(duì)值至多為 k。
示例 1:
輸入: nums = [1,2,3,1], k = 3
輸出: true
示例 2:
輸入: nums = [1,0,1,1], k = 1
輸出: true
示例 3:
輸入: nums = [1,2,3,1,2,3], k = 2
輸出: false
解題思路
在數(shù)組中查找兩個(gè)相等元素并使得其下標(biāo)之差的絕對(duì)值不大于給定值，首先可以想到暴力法去求解，兩層遍歷數(shù)組，查找相等元素對(duì)并判斷其下標(biāo)之差的絕對(duì)值是否小于等于給定值，此解法的時(shí)間復(fù)雜度為O(n^2)。
對(duì)滑動(dòng)窗口有所了解的童鞋，也會(huì)想到通過(guò)滑窗去做。
假設(shè)下標(biāo) i 和 j 對(duì)應(yīng)的元素都相等，且 j - i ≤ k，如下圖示：
由于 j - i ≤ k，則 j 和 i 一定在一個(gè)區(qū)間中，假設(shè)區(qū)間為[len, len + k]，區(qū)間中共有 k + 1 個(gè)元素。
在連續(xù)的有 k + 1 個(gè)元素的區(qū)間中，若能找到兩個(gè)元素其值相等，則能保證其對(duì)應(yīng)下標(biāo)的差一定小于等于 k。
問(wèn)題轉(zhuǎn)化為在數(shù)組中是否能找到一個(gè) k + 1 的區(qū)間，滿足區(qū)間中的兩元素相等。
假如當(dāng)前區(qū)間中，沒(méi)有相等的兩元素，則向右拓展，查看下一元素；同時(shí)減去第一個(gè)元素，len 右移動(dòng)。
查看下一元素 m 在區(qū)間[len + 1, len + k]中是否有相同的元素。
完整過(guò)程，如下動(dòng)圖示：
Show me the Code
「C++」
bool containsNearbyDuplicate(vector<int>& nums, int k) {
/* 創(chuàng)建查找表，滑窗的長(zhǎng)度為查找表的長(zhǎng)度 */
unordered_set<int> record;
for (int i = 0; i < nums.size(); ++i) {
/* 遍歷數(shù)組時(shí)，查找該元素是否在查找表中 */
if (record.find(nums[i]) != record.end()) {
return true;
}
/* 拓展的下一元素跟區(qū)間元素不相等，將其納入?yún)^(qū)間中*/
record.insert(nums[i]);
/* 查找表的長(zhǎng)度超過(guò) k，刪除最左側(cè)元素 */
if (record.size() > k) {
record.erase(nums[i - k]);
}
}
return false;
}
「Java」
boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> record = new HashSet<>();
for (int i = 0; i < nums.length; ++i) {
if (record.contains(nums[i])) {
return true;
}
record.add(nums[i]);
if (record.size() > k) {
record.remove(nums[i - k]);
}
}
return false;
}
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)，其中 n 是數(shù)組的長(zhǎng)度，需要遍歷一遍數(shù)組。
空間復(fù)雜度：O(k)。
滑動(dòng)窗口往期精彩回顧
臉書面試題 leetcode 209. 長(zhǎng)度最小的子數(shù)組(滑動(dòng)窗口)
更多精彩
關(guān)注公眾號(hào)「程序員小熊」
點(diǎn)“贊”和“在看”哦