题目：
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 difference between i and jis at most k.
链接： http://leetcode.com/problems/contains-duplicate-ii/
题解：
用HashMap来保存(nums[i]，i) pair，假如存在相同key并且 i - map.get(key) <= k，返回true。否则遍历完毕以后返回false.
Time Complexity - O(n)， Space Complexity - O(n)
public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { if(nums == null || nums.length == 0) return false; 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; } }
Reference:
原文：http://www.cnblogs.com/yrbbest/p/4990419.html