[054] LeetCode 219演算法【Contains Duplicate III】 包含重複值 III

220. Contains Duplicate III (Medium)

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

這道題目是上一道題目的follow up，這次要求index不能差距大於k，元素大小相差不大於t，且不在乎元素內容是否相同。

這道題目如果有在做大數據的朋友應該很長寫到類似的功能，在某兩個(index)區間範圍內同時符合某些規則(t)，這邊提供幾個思路給大家。

1.傳統暴力解法

首先我們可以知道k是距離，那我們在做比較的時候就可以單純的跳過k個元素做比較(指針再來一根)，在比較是否差距小於t，缺點就是時間複雜度比較高。

2.TreeSet資料結構(binary search)解法

這個問題其實也可以轉換成另一種思路，因為我們身上有一個k要去做距離判斷，再加上t這個距離裡面的兩個數字值不可以超過多少，所以可以換成當前值比它大的最小值，跟比它小的最大值來做判斷。

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

我們用這個來假設，假設到了第一個9，我們可以知道比它大的是沒有，比它小的最大值是5，這種數據結構剛好二元搜索樹可以做到新增、修改、刪除都很快速，缺點就是你必須要知道有這個東西可以用。

3.BucketSort

從上面的理論來看，我們如果有一個統一的資料歸納方式的話，對於處理邏輯會簡單上許多，今天跟各位介紹一種資料分類的方式，

桶排序會把所有資料丟進一個桶子，之後再直接把桶子做插入排序分類，可以說是先集中資料成一箱一箱，最後在用箱子的屬性去做一次排列來完成，這對於面對這種題目，又不知道有甚麼資料結構的朋友來說，有點像是手做一次自己要的資料結構，我是參考這一篇網路資料學習的，不懂的同學可以去看一下，講解的很詳細。

簡易來說就是要定義桶[1-10],[11–21],[21–31],[31–41]…等等，假設我們今天區間為10(t)的話，可以轉換成[0-t],[t+1 - 2t+1],[3t+1 – 4t+1]，假設我們的數字是18，想要找到差距為10的數字區間有誰的話，我們可以去相鄰的兩個桶子裡面找，換言之我們也只需要去相鄰的兩個桶子裡面去找就可以了。

今天你有100個元素，你想要把他分程相對映的桶子編號，並且桶子想要5個桶子做區分，那你的桶子編號設定方式就會是100/5+1，前5個出來的數字會是0，第六個就會是1，以此類推，把他分類好以後再去做判斷，假設在同一個桶子裡面的話就等於他差距是小於等於5才會被計算到同一個桶子裡面，如果是前一個或後一個桶子有可能會這樣，假設我目前是7，但前一個桶子裝的是4，那差距還是5以下，所以要對前一個跟後一個桶子做判斷。

大家加油。

上一篇：[053] LeetCode 219演算法【Contains Duplicate II】 包含重複值 II

下一篇：[055] LeetCode 55演算法【Jump Game】 跳躍遊戲