題目在問什麼

給一個整數陣列 nums 和整數 k，判斷是否存在兩個不同索引 i、j，使得：

  • nums[i] == nums[j]
  • |i - j| <= k

例子

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

解題思路

這題和一般 Contains Duplicate 的差別，在於不是只看有沒有重複，而是要看重複元素之間的索引距離。

所以最自然的做法是用 Dictionary<int, int> 記錄：

  • key: 元素值
  • value: 這個值最近一次出現的索引

遍歷陣列時：

  1. 如果當前值之前出現過，就先算和上次索引的距離
  2. 若距離 <= k，直接回傳 true
  3. 不管有沒有成功，都把字典中的索引更新成最新位置

為什麼只記最近一次就夠

因為如果某個值在更早之前出現過，但距離已經超過 k，那它之後能不能成立，只會和更靠近現在的那次出現有關。

所以保留最新索引就足夠，不需要把所有位置都存下來。

代碼

public class Solution
{
    public bool ContainsNearbyDuplicate(int[] nums, int k)
    {
        if (k == 0) { return false; }

        Dictionary<int, int> idxDict = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++)
        {
            if (idxDict.ContainsKey(nums[i]))
            {
                if (i - idxDict[nums[i]] <= k)
                {
                    return true;
                }
            }

            idxDict[nums[i]] = i;
        }

        return false;
    }
}

複雜度

  • 時間複雜度：O(n)
  • 空間複雜度：O(n)

這題先記住的重點

  • 這題核心不是「有沒有重複」，而是「重複元素距離夠不夠近」
  • 字典裡只保留最近一次出現的位置就夠了
  • 這是一題很標準的「值到索引」映射題