Array - 219. Contains Duplicate II

ppxai

发布于 2020-09-23 17:07:59

2630

发布于 2020-09-23 17:07:59

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
}```

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年06月12日，如有侵权请联系 cloudcommunity@tencent.com 删除

absolute