LeetCode Notes: Contains Duplicate II

#leetcode

Question

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.

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

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

Solution One

Analysis:

Use an object to store the information of each number, using the principle that the key cannot be repeated, each time a new repeated number is encountered, the position information and the absolute value of the most recent repeated number are updated. Once an absolute value is smaller than k it is to successfully find the number you want.

Code:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    // Initialize storage space
    const obj = {};

    // Just loop once, traverse all the numbers
    for(let i = 0; i < nums.length; i++){
        // current number
        const n = nums[i]

        // Whether there are duplicate numbers
        if(n in obj){
            // For repeated numbers, the absolute value needs to be updated to the difference with the previous value, because the difference with the previous one must be smaller
            obj[n].abs = i-obj[n].i;
            // After calculating the difference above, you can update the current position, which is used to calculate the difference when it repeats the next time
            obj[n].i = i;
            
            // Once the current difference is found to be less than k, the condition is met and exit
            if(obj[n].abs <= k) return true;
        }else{
            // Initialize the number that appears for the first time, store the location and absolute value (because it appears for the first time, the absolute value is 0)
            obj[n] = {
                i:i,
                abs:0
            }
        }
    }

    //If the number that meets the conditions is not found in the above loop, it will return `false` by default
    return false
};

Solution Two

Analysis:

Make use of the feature of Set that no repeated elements are allowed, make a sliding window of k size, and slide forward to find whether the same element appears in the window. This sliding window requires less space.

Code:

/**
  * @param {number[]} nums
  * @param {number} k
  * @return {boolean}
  */
var containsNearbyDuplicate = function(nums, k) {
     const set = new Set();
     for(let i = 0; i < nums.length; i++){
         // Once repeated elements appear in the sliding window, the requirements are met
         if(set.has(nums[i])){
             return true
         }
         // Every value is added
         set.add(nums[i]);

         // Once the number exceeds k, delete the first number, that is, the sliding window moves to the right
         if(set.size> k){
             set.delete(nums[i-k]);
         }
     }
     return false
};

Reference

Comments