LeetCode Js-219. Contains Duplicate II

    AllenLi
    LeetCode Js-Array

    Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i – j) <= k. 

    給予一個整數陣列 nums，和一個整數 k，如果有兩個重複值得索引 i 和 j 在這個陣列中，且符合以下條件，則回傳 true。
1. nums[i] == nums[j]
2. abs(i – j) <= k

    Example 1:

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

    Example 2:

    Input: nums = [1,0,1,1], k = 1
Output: true

    Example 3:

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

    Solution:
    1. 判斷是否有重複的數字，沒有直接返回 false。
    2. 宣告 box 物件{}。
    3. 依序將 nums 放入 box{}。
    4. 加入判斷式，且同時符合，則回傳 true：

    1. 物件特性找出有出現過的數值。
2. 重複出現的數值索引 i 和 j，兩者之間的距離小於等於 k。

    5. 將 box[] 數值放入對應的索引。
    6. 皆不符合，回傳 false。

    Code 1: BigO(n)

    var containsNearbyDuplicate = function(nums, k) {
  if (nums.length <= 1) return false //只有一個數值，條件不成立，故提前結束。

  let box = {}
  for (let i in nums) {
    let j = nums[i]
   
    if (box[j] && ((i - box[j]) <= k)) {
      return true
    }
    box[j] = i
  }
  return false
};

    FlowChart:
    Example 1

    Input: nums = [1,2,3,1], k = 3
nums.length = 4 >= 1

step.1
box = {}
i = 0, j = 1, box[1] = undefined => false |box[1] = 0 => {'1': 0}
i = 1, j = 2, box[2] = undefined => false |box[2] = 1 => {'1': 0, '2': 1} 
i = 2, j = 3, box[3] = underfined => false |box[3] = 2 => {'1': 0, '2': 1, '3': 2}  
i = 3, j = 1, box[1] && ((3 - box[1]) <= k) 
               //  0 && ((3 - 1) <= 3) => return true

    Example 2

    Input: nums = [1,0,1,1], k = 1
nums.length = 4 >= 1

step.1
box = {}
i = 0, j = 1, box[1] = undefined => false |box[1] = 0 => {'1': 0}
i = 1, j = 0, box[0] = undefined => false |box[0] = 1 => {'0': 1, '1': 0} 
i = 2, j = 1, box[1] = 0 && ((2 - box[1]) <= k) => false |box[1] = 2 => {'0': 1, '1': 2} 
i = 3, j = 1, box[1] = 2 && ((3 - box[1]) <= k) => true

    Example 3

    Input: nums = [1,2,3,1,2,3], k = 2
nums.length = 6 >= 1

step.1
box = {}
i = 0, j = 1, box[1] = undefined => false |box[1] = 0 => {'1': 0}
i = 1, j = 2, box[2] = undefined => false |box[2] = 1 => {'1': 0, '2': 1}
i = 2, j = 3, box[3] = undefined => false |box[3] = 2 => {'1': 0, '2': 1, '3': 2}
i = 3, j = 1, box[1] = 0 && ((3 - box[1]) <= k) => false |box[1] = 3 => {'1': 3, '2': 1, '3': 2}
i = 4, j = 2, box[2] = 1 && ((4 - box[2]) <= k) => false |box[2] = 4 => {'1': 3, '2': 4, '3': 2}
i = 5, j = 3, box[3] = 2 && ((5 - box[3]) <= k) => false |box[3] = 5 => {'1': 3, '2': 4, '3': 5}

return false

    Code 2: BigO(n)

    var containsNearbyDuplicate = function (nums, k) {
    if (nums.length <= 1) return false;
    const hashTable = {}

    for (let i = 0; i < nums.length; i++) {
        if (hashTable[nums[i]] !== undefined && (i - hashTable[nums[i]] <= k)) return true;
        hashTable[nums[i]] = i
    }
    return false;
};

    Code 3: Sliding Window BigO(n)

    var containsNearbyDuplicate = function(nums, k) {
  const set = new Set()
  for (let i = 0; i < nums.length; i++) {
    if (set.has(nums[i])) return true;

    set.add(nums[i])

    if (set.size > k) {
      set.delete(nums[i - k])
    }
  }
  return false;
};

    Related Posts