文章 224
评论 6
浏览 200762
Array - 219. Contains Duplicate II

Array - 219. Contains Duplicate II

219、Contains Duplicate II

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

思路:

这题是217题的变形,多加了在k范围内重复才返回true,思路也是使用map来做,遍历的同时查重,时间复杂度O(N),空间复杂度为O(N),使用滑动窗口的思想可以优化空间复杂度为O(K)。

代码:

java:

class Solution {

    // solution 1 hashmap. time: O(n) space: O(n)
    /*public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length == 0) return false;
        
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0;  i < nums.length; i++) {
            Integer index = map.get(nums[i]);
            if (index != null && i-index <= k){
                return true;
            }
            
            map.put(nums[i], i);
        }
        
        return false;
    }*/
    
    // solution 2 Sliding Window. time: O(n) space: O(k)
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length == 0) return false;
        
        HashSet<Integer> set = new HashSet();
        for (int i = 0;  i < nums.length; i++) {
           if (!set.add(nums[i])) {
               return true;
           }
            
           // 更新set,保证大小不超过k
           if (i >= k) {
               set.remove(nums[i - k]);
           }
        }
        
        return false;
    }
  
} // best case

go:


/*func containsNearbyDuplicate(nums []int, k int) bool {
    if nums == nil || len(nums) == 0 { return false }

    var (
        maps   = make(map[int]int)
        window = make([]int, 0) 
    )
    
    for i, v := range nums {
        if _, ok := maps[v]; ok{
            return true
        } else {
            maps[v] = i
            window = append(window, v)
        }
        
        // update map size if we have more than k
        if (i >= k) {
            delete(maps, window[0])
            window = window[1:]
        }
    }
    
    return false 
}
//bad case */

func containsNearbyDuplicate(nums []int, k int) bool {
    exist := make(map[int]int, len(nums))
    for i, v := range nums{
        if pos, ok := exist[v]; ok && i - pos <= k{
            return true
        }
        exist[v] = i
    }
    return false
}```

标题:Array - 219. Contains Duplicate II
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/06/12/1560352577752.html

Nothing just happens, it's all part of a plan.

取消