存在重復元素 II

• 給你一個整數數組 nums 和一個整數 k ，判斷數組中是否存在兩個 不同的索引 i 和 j ，
• 滿足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；
• 否則，返回 false 。

示例 1：

輸入：nums = [1,2,3,1], k = 3
輸出：true

解題思路

• 使用哈希表（HashMap）來記錄每個元素最后一次出現的索引。
• 遍歷數組時，檢查當前元素是否已經在哈希表中存在且索引差小于等于 k。
• 如果存在這樣的元素，則返回 true；
• 如果遍歷完整個數組后沒有找到這樣的元素，則返回 false。

Java實現

public class ContainsNearbyDuplicate {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {return true;}map.put(nums[i], i);}return false;}public static void main(String[] args) {ContainsNearbyDuplicate solution = new ContainsNearbyDuplicate();// Test Case 1int[] nums1 = {1, 2, 3, 1};int k1 = 3;System.out.println("Test Case 1:");System.out.println("Result: " + solution.containsNearbyDuplicate(nums1, k1)); // Expected: true// Test Case 2int[] nums2 = {1, 2, 3, 1, 2, 3};int k2 = 2;System.out.println("\nTest Case 2:");System.out.println("Result: " + solution.containsNearbyDuplicate(nums2, k2)); // Expected: false}
}

時間空間復雜度

• 時間復雜度：遍歷數組一次，時間復雜度為 O(n)，其中 n 是數組的長度。

• 空間復雜度：使用了一個哈希表來存儲元素及其索引， 最壞情況下需要存儲 n 個元素，因此空間復雜度為 O(n)