My-LeetCode-solutions/lc-219.java at master · nerozenJL/My-LeetCode-solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//use set
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet();
        for(int i = 0; i<nums.length; i++) {
            if(set.contains(nums[i])) {
                for(int j = i-1; j>=0 && (i-j)<=k; j--) {
                    if(nums[i] == nums[j]) {
                        return true;
                    }
                }
            }else{
                set.add(nums[i]);
            }
        }
        return false;
    }
}


//brute force O(n*k) 最坏时间O(n^2)，TLE
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for(int i = 0; i<nums.length; i++) {
            for(int j = 1; j<=k; j++) {
                if(i+j<nums.length) {
                    if(nums[i] == nums[i+j]) return true;
                }else {
                    break;
                }
            }
        }
        return false;
    }
}