Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/219.html

219. Contains Duplicate II

Level

Easy

Description

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most 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

Use a Map to store each number and the last index at which the number occurred. Loop over the array from left to right. At each index, obtain the number at the current index and find the last index of the number. If the number has already occurred before and the difference between the current index and the previous index is less than or equal to k, then return true. If there isn’t such a number that has its two occurrences differing by k at most, then return false.

Code

• Java
• C++
• Python
• Go
• TypeScript
• C#
• Php

• import java.util.HashMap;
  import java.util.Map;
  
  public class Contains_Duplicate_II {
  
      public class Solution {
          public boolean containsNearbyDuplicate(int[] nums, int k) {
  
              // value => index
              Map<Integer, Integer> map = new HashMap<>();
              for (int i = 0; i < nums.length; i++) {
                  // 如果3个repeat，那么也是put到map，把第一个丢掉
                  if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                      return true;
                  }
                  map.put(nums[i], i);
              }
              return false;
          }
      }
  }
  
  ############
  
  class Solution {
      public boolean containsNearbyDuplicate(int[] nums, int k) {
          Map<Integer, Integer> mp = new HashMap<>();
          for (int i = 0; i < nums.length; ++i) {
              if (mp.containsKey(nums[i]) && i - mp.get(nums[i]) <= k) {
                  return true;
              }
              mp.put(nums[i], i);
          }
          return false;
      }
  }
  

• // OJ: https://leetcode.com/problems/contains-duplicate-ii/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      bool containsNearbyDuplicate(vector<int>& A, int k) {
          unordered_map<int, int> m;
          for (int i = 0; i < A.size(); ++i) {
              if (m.count(A[i]) && i - m[A[i]] <= k) return true;
              m[A[i]] = i;
          }
          return false;
      }
  };
  

• class Solution:
      def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
          mp = {}
          for i, v in enumerate(nums):
              if v in mp and i - mp[v] <= k:
                  return True
              mp[v] = i
          return False
  
  ############
  
  from collections import deque
  
  
  class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
      """
      :type nums: List[int]
      :type k: int
      :rtype: bool
      """
      if not nums:
        return False
      if k == 0:
        return False
      k = k + 1
      k = min(k, len(nums))
  
      window = deque([])
      d = set()
      for i in range(0, k):
        if nums[i] in d:
          return True
        d |= {nums[i]}
        window.append(i)
      for i in range(k, len(nums)):
        d -= {nums[window.popleft()]}
        if nums[i] in d:
          return True
        d |= {nums[i]}
        window.append(i)
      return False
  
  

• func containsNearbyDuplicate(nums []int, k int) bool {
  	mp := make(map[int]int)
  	for i, v := range nums {
  		if j, ok := mp[v]; ok {
  			if i-j <= k {
  				return true
  			}
  		}
  		mp[v] = i
  	}
  	return false
  }
  

• function containsNearbyDuplicate(nums: number[], k: number): boolean {
      const map = new Map();
      for (let i = 0; i < nums.length; i++) {
          const t = nums[i];
          if (map.has(t) && i - map.get(t) <= k) {
              return true;
          }
          map.set(t, i);
      }
      return false;
  }
  
  

• public class Solution {
      public bool ContainsNearbyDuplicate(int[] nums, int k) {
          var mp = new Dictionary<int, int>();
          for (int i = 0; i < nums.Length; ++i)
          {
              if (mp.ContainsKey(nums[i]) && i - mp[nums[i]] <= k)
              {
                  return true;
              }
              mp[nums[i]] = i;
          }
          return false;
      }
  }
  

• class Solution {
      /**
       * @param Integer[] $nums
       * @param Integer $k
       * @return Boolean
       */
      function containsNearbyDuplicate($nums, $k) {
          $hashtable = [];
          for ($i = 0; $i < count($nums); $i++) {
              $tmp = $nums[$i];
              if (
                  array_key_exists($tmp, $hashtable) &&
                  $k >= $i - $hashtable[$tmp]
              ) {
                  return true;
              }
              $hashtable[$tmp] = $i;
          }
          return false;
      }
  }
  
  

All Problems

All Solutions