Contains Duplicate II

https://leetcode.com/problems/contains-duplicate-ii/description/

Given an array of integers and an integerk, find out whether there are two distinct indicesiandjin the array such thatnums[i] = nums[j]and theabsolutedifference betweeniandjis at mostk.

Thoughts

问两个坑是否装同一个数，且坑的indexの差小于k. 遍历，如果当前元素在map中则计算它和当前index的差。map更新为当前的i, 因为要求找最近的，当后面还出现该元素时和i的diff肯定比和i之前的diff小。

Code

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }

        return false;
    }
}

Analysis

时间空间都是O(n).