LeetCode-219

发表于   |   分类于   |  

Contains Duplicate II

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

题目大意：

给定一个整数数组nums与一个整数k，当且仅当存在两个不同的下标i和j满足nums[i] = nums[j]并且| i - j | <= k时返回true，否则返回false。

解题思路：

  1. 当且仅当说明整个数组里有且只有两个数字相同，而且它们的下标差绝对值不大于k。
  2. 返回为true的可能性要小，有特殊性（在k个字符内有且仅有两个相同的字符）。所以，可以用k长的窗口，在窗口里去判断是否有相同的字符，而字符的唯一性，设置一个变量来记录。
  3. 尽量使用复杂度低的算法，该算法时间复杂度为O(N)的。

实现方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> appearedNum = new HashSet<Integer>();  
        int start = 0, end = 0, num=0;  
        for(int i = 0; i < nums.length; i++){  
            if(!appearedNum.contains(nums[i])){  
                appearedNum.add(nums[i]);  
                end++;  //窗口往后移动
            } 
            else num++;  //确定唯一性
            if(end - start  > k) {  
                appearedNum.remove(nums[start]);  //时刻保持appearedNum里只有k个字符
                start++;  
            }  
        }
        if(num==1) //判断是否唯一
        return true;
        return false;  
    }
}