美文网首页Leetcode每日两题程序员
Leetcode 219. Contains Duplicate

Leetcode 219. Contains Duplicate

作者: ShutLove | 来源:发表于2017-11-28 13:02 被阅读14次

    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.

    思路:用哈希表记录数字对应的位置,遍历数组,如果哈希表中已存在此数字,更新相距的最短距离,如果最短距离小于等于k,则返回true。

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k < 1) {
            return false;
        }
    
        //record num => pos
        HashMap<Integer, Integer> map = new HashMap<>();
    
        //min distance
        int minDistance = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                minDistance = Math.min(minDistance, i - map.get(nums[i]));
                if (minDistance <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
    
        return false;
    }

    相关文章

      网友评论

        本文标题:Leetcode 219. Contains Duplicate

        本文链接:https://www.haomeiwen.com/subject/bkwsbxtx.html