[LintCode/LeetCode] Contains Duplicate II

894974231 发布于2019-08-19 10:48 / 1274人阅读

Problem

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

Given nums = [1,2,1], k = 0, return false.

Solution

public class Solution {
    /**
     * @param nums: the given array
     * @param k: the given number
     * @return:  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
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // Write your code here
        if (nums.length < 2 || k < 1) return false;
        Set set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            // i - (i-k-1) > k
            if (i > k) set.remove(nums[i-k-1]);
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
        }
        return false;
    }
}

也可以用HashMap的简单解法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76465.html

[LintCode/LeetCode] Subsets & Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate III

Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute dif...

MageekChiu 2019-08-19 10:48 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] Remove Duplicate Letters

Problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical...

wanghui 2019-08-15 18:01 评论0 收藏0
[LintCode/LeetCode] Single Number I & II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0