leetcode-219-Contains-Duplicate-II

发表于   |  

描述

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 j is at most k.

分析

给定一个数组，如果有两个相等的元素下标之差不大于k就返回true。
要获得相同元素最小的下标差，那么这两个元素必然是相邻的（相同元素的序列中相邻），所以用一层循环即可，复杂度是O(n), 用一个hash表存元素对应的下标，循环中，第一次遇到就在hash表中新建一项，再遇到就做判断，如果大于k就更新该元素对应的下标值（所以进行比较的总是相邻的相等的元素）

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> map_value_index;
        map<int, int>::iterator iter;
        for(int i = 0; i < nums.size(); i++) {
            if((iter=map_value_index.find(nums[i])) != map_value_index.end()) {     // 如果hash表中已经有该值
                if(i - iter->second <= k) {
                    return true;
                }else {
                    map_value_index.erase(iter);
                }
            }
            map_value_index.insert(pair<int, int>(nums[i], i));
        }
        return false;
    }
};

解决方案2(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map_value_index = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums.length; i++) {
            if(map_value_index.containsKey(nums[i])) {
                if(i - map_value_index.get(nums[i]) <= k) {
                    return true;
                }else {
                    map_value_index.remove(nums[i]);
                }
            }
            map_value_index.put(nums[i], i);  
        }
        return false;
    }
}

解决方案3(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        d = {}    # 用来存放hash表
        for i in range(len(nums)):
            if nums[i] in d:              # 如果hash表中已经存在该值
                if i - d[nums[i]] <= k:   # 和C++,Java的map不同，这里的字典可以覆盖，不必删除
                    return True
            d[nums[i]] = i
        return False

相关问题

(E) Contains Duplicate
(M) Contains Duplicate III

题目来源

P.S.

翻看了一下论坛，发现大家的思路大致相同。这里用C++，java，Python实现的思路是相同的，可以从这道题窥探一下这几种语言的不同特性。