LeetCode演算法題-Contains Duplicate II（Java實現）
這是悅樂書的第193 次更新，第197 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第53題（順位題號是219）。給定整數陣列和整數k，找出陣列中是否存在兩個不同的索引i和j，使得nums [i] = nums [j]並且i和j之間的絕對差值小於等於k。例如：
輸入：nums = [1,2,3,1]，k = 3
輸出：true
輸入：nums = [1,0,1,1]，k = 1
輸出：true
輸入：nums = [1,2,3,1,2,3]，k = 2
輸出：false
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
利用hashMap，依次遍歷陣列元素，如果當前元素不存在就put進map，如果存在，則說明具有重複元素，然後獲取當前索引與此元素在map中的索引value值的絕對值，判斷其是否小於等於k，如果滿足，則返回true。
此解法因為用到了map.containsKey()方法，所以時間複雜度最好的情況是O(n)，最壞的情況是O(n^2)，空間複雜度是O(n)。
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
if (map.containsKey(nums[i]) && Math.abs(i-map.get(nums[i])) <= k) {
return true;
} else {
map.put(nums[i], i);
}
}
return false;
}
03 第二種解法
如果滿足題目的條件，nums[i] = nums[j]，並且j-i <= k，那麼只要nums[i]等於nums[i+1]至nums[i+k]之間的任意一個，即可返回true。使用兩層for迴圈，外層控制從1到k，內層遍歷陣列元素，如果外層指標加上內層指標小於陣列大小，並且兩指標對應的元素相等，則返回true。
此解法的時間複雜度是O(kn)，最好的情況是O(n)，最壞的情況是O(n^2)，空間複雜度是O(1)。 此解法會超時 *。
public boolean containsNearbyDuplicate2(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
for (int i=1; i<= k; i++) {
for (int j=0; j<nums.length; j++) {
if (j+i < nums.length && nums[j] == nums[j+i]) {
return true;
}
}
}
return false;
}
04 第三種解法
此解法與上面第二種解法的思路一致，不過是將內外層迴圈換了位置，並且內層迴圈判斷nums[i]和nums[j]相等時，對於指標的範圍做了調整，從陣列長度、i+1+k之間取最小值。
public boolean containsNearbyDuplicate3(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
for (int i=0;i < nums.length; i++) {
for (int j=i+1; j<Math.min(nums.length, i+1+k); j++) {
if (nums[i] == nums[j]) {
return true;
}
}
}
return false;
}
05 第四種解法
利用HashSet。此解法的程式碼和昨天的那道題沒多大區別，只不過是在迴圈判斷true或false的前面，加多了一個判斷，如果當前的指標i大於k，那麼就將HashSet中的nums[i - k - 1]元素刪除，即當i>k的時候，將HashSet從第1一個元素開始移除，表示前k個元素已經不符合題目的條件了，並且隨著迴圈繼續，會依次刪除不符合的元素。
public boolean containsNearbyDuplicate4(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (i > k) {
set.remove(nums[i - k - 1]);
}
if (!set.add(nums[i])) {
return true;
}
}
return false;
}
06 第五種解法
使用雙指標。迴圈內判斷true或false的地方，如果兩指標不相等，並且其各自所指向的元素相等，則返回true。第二個判斷是移動兩個指標的關鍵，兩個指標初始值都是0，如果兩指標的差小於k，則其中做一個指標加1，否則另外一個指標加1，即判斷相隔小於k位之間的元素是否相等。
public boolean containsNearbyDuplicate5(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k == 0) {
return false;
}
int p1 = 0;
int p2 = 0;
while (p1 < nums.length) {
if (nums[p1] == nums[p2] && p1 != p2) {
return true;
}
if (p2 - p1 < k && p2 < nums.length - 1) {
p2++;
} else {
p1++;
}
}
return false;
}
07 小結
演算法專題目前已連續日更超過一個月，演算法題文章53 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！