[LintCode/LeetCode] Contains Duplicate II

894974231 發(fā)布于2019-08-19 10:48 / 1305人閱讀

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的簡單解法

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.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 [位運算]

摘要：整個過程相當于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 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