219. 存在重复元素 II

Posted on | In
Words count in article: 537 | Reading time ≈ 2

题目

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例1：

1
2
输入: nums = [1,2,3,1], k = 3
输出: true

示例2：

1
2
输入: nums = [1,0,1,1], k = 1
输出: true

示例3：

1
2
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

解法

解法一：

遍历数组，假设当前数字索引为i，那么计算从i+1 到i+k是否有其相同的元素，有返回true，否则继续判断下一个数字

Java

1
2
3
4
5
6
7
8
9
10
11
12
public boolean containsNearbyDuplicate(int[] nums, int k) {
		for (int i = 0;i < nums.length;i++) {
			int count = 1;
			while (count <= k && i + count < nums.length) {
				if (nums[i] == nums[i + count]) {
					return true;
				}
                count++;
			}
		}
		return false;
    }

解法二：

借助HashMap。

遍历数组，在遍历的过程中，判断该数字是否已经存在HashMao中了。

如果已经存在，挨个计算它之前的索引和当前索引差是否超过k，没有则返回true；

否则把当前索引加入索引列表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean containsNearbyDuplicate(int[] nums, int k) {
		Map<Integer, List<Integer>> map = new HashMap<>();

		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(nums[i])) {
				List<Integer> list = map.get(nums[i]);
				for (int num : list) {
					if (k >= Math.abs(num - i)) {
						return true;
					} 
				}
				map.get(nums[i]).add(i);
			} else {
				List<Integer> list = new ArrayList<>();
				list.add(i);
				map.put(nums[i], list);
			}
		}
		return false;
	}

解法三：

使用HashSet。

遍历数组，对于每个元素做以下操作：

  1. 在散列表中搜索当前元素，如果找到了就返回 true。
  2. 在散列表中插入当前元素。
  3. 如果当前散列表的大小超过了 kkk， 删除散列表中最旧的元素。

返回false

1
2
3
4
5
6
7
8
9
10
11
12
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])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

0%