66 - 存在重复元素2

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

解答

两个相同值，索引的最大差值为k。

set

作者：guanpengchn

链接：https://leetcode-cn.com/problems/contains-duplicate-ii/solution/hua-jie-suan-fa-219-cun-zai-zhong-fu-yuan-su-ii-by/

设置一个set，最多存k个数，在遍历的时候如果发现了相同值，那么就说明找到了。

官网管这个叫散列表。。似乎一下子就高大上了呢。。

var containsNearbyDuplicate = function (nums, k) {
  let scope = new Set()
  for (let i = 0; i < nums.length; i++) {
    if (scope.has(nums[i])) {
      return true
    }
    scope.add(nums[i])
    if (scope.size > k) {
      scope.delete(nums[i - k])
    }
  }
  return false
};

Runtime: 52 ms, faster than 99.64% of JavaScript online submissions for Contains Duplicate II.

Memory Usage: 39 MB, less than 78.95% of JavaScript online submissions for Contains Duplicate II.

可惜set不能用set[0]这样的方法来取第一个元素，或者说就没有现成的方法取得到第一个元素。只能计算一下set中的第一个元素。

用array 呢？

var containsNearbyDuplicate = function (nums, k) {
  let scope = []
  for (const item of nums) {
    if (scope.indexOf(item) !== -1) {
      return true
    }
    scope.push(item)
    if (scope.length > k) {
      scope = scope.slice(1)
    }
  }
  return false
};

Runtime: 3456 ms, faster than 5.09% of JavaScript online submissions for Contains Duplicate II.

Memory Usage: 58.8 MB, less than 5.26% of JavaScript online submissions for Contains Duplicate II.

是真滴慢。。

如果换成shift 呢？

...
if (scope.length > k) {
  scope.shift()
}
...

Runtime: 1376 ms, faster than 11.15% of JavaScript online submissions for Contains Duplicate II.

Memory Usage: 39.1 MB, less than 73.68% of JavaScript online submissions for Contains Duplicate II.

稍微快了一点

似乎slice的做法是要建立一个新的数组，来放切片后的数组。因此会有很大的成本。

哈希表似乎也可以

var containsNearbyDuplicate = function (nums, k) {
  let scope = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (scope.has(nums[i])) {
      return true
    }
    scope.set(nums[i], true)
    if (scope.size > k) {
      scope.delete(nums[i - k])
    }
  }
  return false
};

Runtime: 64 ms, faster than 84.85% of JavaScript online submissions for Contains Duplicate II.

Memory Usage: 40.2 MB, less than 57.89% of JavaScript online submissions for Contains Duplicate II.

go

go里面没有set，就用map做了

func containsNearbyDuplicate(nums []int, k int) bool {
    scope := make(map[int]bool)
    for i := 0; i < len(nums); i++ {
        if _, ok := scope[nums[i]]; ok {
            return true
        }
        scope[nums[i]] = true
        if len(scope) > k {
            delete(scope, nums[i-k])
        }
    }
    return false
}

Runtime: 16 ms, faster than 74.58% of Go online submissions forContains Duplicate II.

Memory Usage: 6.8 MB, less than 33.33% of Go online submissions forContains Duplicate II.

go的很多语法都不一样了

• map的创建用make

• 添加有点像js的obj

• 删除就直接用一个delete函数。。估计是装在map下面的

• 长度就是len()来计算的

go的delete函数是贴在map下面的，这样的话我们定义一个delete函数，就能把go的自带函数覆盖掉了。。。

go虽然可以用slice来创建一个固定长度的数组，但是没有现成api来查找有没有某个元素，只能自己写一个for-range来找。这就很麻烦也不划算了。

因此遇到需要检查某元素是否存在的，直接用map就完事了，多费一个true的空间也没办法。