1, 题目

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

  1. 输入: nums = [1,2,3,1], k = 3
  2. 输出: true

示例 2:

  1. 输入: nums = [1,0,1,1], k = 1
  2. 输出: true

示例 3:

  1. 输入: nums = [1,2,3,1,2,3], k = 2
  2. 输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. object Solution {
  2.     def containsNearbyDuplicate(nums: Array[Int], k: Int): Boolean = {
  3.         val m = scala.collection.mutable.Map[Int, Int]()
  4.         for ((value, index) <- nums.zipWithIndex) {
  5.             if (m.contains(value)) {
  6.                 if ((index - m(value)).abs <= k) {
  7.                     return true
  8.                 } else {
  9.                     m(value) = index
  10.                 }
  11.             } else {
  12.                 m(value) = index
  13.             }
  14.         }
  15.         false
  16.     }
  17. }
  1. class Solution:
  2.     def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
  3.         m = {}
  4.         for i, x in enumerate(nums):
  5.             if x in m:
  6.                 if abs(i - m[x]) <= k:
  7.                     return True
  8.                 else:
  9.                     m[x] = i
  10.             else:
  11.                 m[x] = i
  12.         return False