查找下标满足一定条件的重复 Contains Duplicate II

原创
2017/05/16 21:10
阅读数 8

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.

解决方法:

①暴力破解。直接双重循环查找满足下标之差不大于K的数是否有重复的,若有,则返回true。否则,返回false。这种方法超时。

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0;i <nums.length ;i ++ ) {
            for (int j = i + 1;j <= k + i && j < nums.length;j ++ ) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

②使用HashMap。将数组中的值和下标依次存储到map中,同时查找之前存入的值是否有与它相等的值,计算它们之间的距离,看是否满足要求。用时20ms。

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

若先保存到map中再查找,则会有重复的key值,无法区分满足条件的是哪些。

③使用HashSet,它在使用add()方法时,若set中不存在,则直接插入并返回true,否则,返回false。在下面的方法中使用了它的这一特性,使用set保存k个值,当插入大于k时,就删去前面的数。此时,若插入时返回false,就表示这两个相同的值在k个距离以内。

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0;i <nums.length ;i ++ ) {
            if (i > k) { //使用一个滑动窗口,使用set保存这k个值,之前的值均被删除。不能加=,因为输入为[-1,-1] 1时,结果错误
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {//若添加时返回false,表示这k个值中包含该值,满足题意,返回true
                return true;
            }
        }
        //否则返回false
        return false;
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部