圖解 | LeetCode #219 存在重復(fù)元素||

????關(guān)注后回復(fù) “進(jìn)群” ，拉你進(jìn)程序員交流群????

作者丨微木

來(lái)源丨編程狂想曲

你好，我是微木。

今天分享的內(nèi)容是LeetCode中219.存在重復(fù)元素|| 簡(jiǎn)單 這個(gè)題目。

題目描述：

給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的絕對(duì)值至多為 k。

示例:

輸入: nums = [1,2,3,1,2,3], k = 2

輸出: false

思路分析
根據(jù)題目描述，有兩點(diǎn)需要思考：
一是nums[i]=nums[j]。
要判斷數(shù)組中有沒(méi)有重復(fù)值，可以對(duì)數(shù)組進(jìn)行遍歷。對(duì)于每一個(gè)要考察的元素，先判斷HashSet中有沒(méi)有該元素。有，則找到了重復(fù)元素；沒(méi)有，則將當(dāng)前考察元素存入HashSet。這里為什么用HashSet，文末分析。
二是兩個(gè)不同的索引i和j的差的絕對(duì)值至多為k。
拿示例nums = [1,2,3,1,2,3], k = 2來(lái)說(shuō)，前三個(gè)元素是1、2、3，當(dāng)考察到元素3時(shí)，此時(shí)，元素3對(duì)應(yīng)的索引為2，元素1對(duì)應(yīng)的索引為0，兩者之差的絕對(duì)值為2等于k=2。
這時(shí)，要繼續(xù)考察下一個(gè)元素1，則第一個(gè)元素1就不在考察范圍內(nèi)了。因?yàn)?，如果第一個(gè)元素1還在考察范圍內(nèi)的話，雖然找到了兩個(gè)一樣的元素1，但它兩的索引差值是3大于k=2。
這說(shuō)明什么呢？說(shuō)明，要在一個(gè)窗口內(nèi)尋找有沒(méi)有相等的元素。
經(jīng)過(guò)上述分析，該題目的的解題方法是滑動(dòng)窗口和Set相結(jié)合來(lái)求解。
具體代碼實(shí)現(xiàn)如下：
對(duì)于上述代碼實(shí)現(xiàn)，有兩點(diǎn)說(shuō)明一下：
為什么窗口內(nèi)最多能容納k+1個(gè)元素？
對(duì)于示例nums = [1,2,3,1,2,3], k = 2。先將前三個(gè)元素，即k+1個(gè)元素存入set。動(dòng)畫演示如下：
在將前3個(gè)元素存入set后，下一個(gè)待考察元素是1，它的索引是3，其值和索引為0的元素1是相等的。但，它兩之間索引的差值為3-0=3，大于k=2，因此，set中最多容納k+1個(gè)元素。

為什么從set中移除元素時(shí)，移除的是nums[i-k]這個(gè)元素？
上述分析了為什么set中最多容納k+1個(gè)元素。對(duì)于示例nums = [1,2,3,1,2,3], k = 2來(lái)說(shuō)，當(dāng)set中已經(jīng)有k+1等于3個(gè)元素時(shí)，為了繼續(xù)考察下一個(gè)元素，就需要將滑動(dòng)窗口左側(cè)的元素移除，即nums[i-k]=nums[2-2]=nums[0]這個(gè)元素需要從窗口左側(cè)移除。i代表當(dāng)前考察的元素對(duì)應(yīng)的索引。
在上述的代碼實(shí)現(xiàn)中，用的是HashSet來(lái)判斷窗口內(nèi)是否有重復(fù)元素。那么，能不能用LinkedList和ArrayList呢？
用LinkedList時(shí)，代碼實(shí)現(xiàn)如下：
提交后提示超時(shí)，為什么呢？原因在于，LinkedList是用鏈表實(shí)現(xiàn)的，在鏈表中查找一個(gè)元素是否存在時(shí)，要遍歷整個(gè)鏈表，增加了時(shí)間復(fù)雜度。
用ArrayList時(shí)，代碼實(shí)現(xiàn)如下：
提交后同樣提示超時(shí)，為什么呢？原因在于，ArrayList是用數(shù)組實(shí)現(xiàn)的，每次為了保證窗口內(nèi)的元素最多為k+1個(gè)，在移除第一個(gè)元素后，后面的元素都有向前移動(dòng)一個(gè)位置，增加了時(shí)間復(fù)雜度。

-End-

最近有一些小伙伴，讓我?guī)兔φ乙恍?nbsp;面試題 資料，于是我翻遍了收藏的 5T 資料后，匯總整理出來(lái)，可以說(shuō)是程序員面試必備！所有資料都整理到網(wǎng)盤了，歡迎下載！

點(diǎn)擊??卡片，關(guān)注后回復(fù)【面試題】即可獲取

在看點(diǎn)這里好文分享給更多人↓↓