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 absolute difference between i and j is at most k.
第一想法就是把每种情况都列一下,复杂度O(kn)。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i=0; i<n-1; i++)
            for (int j=i+1; j<=i+k && j<n; j++)
                if (nums[i] == nums[j])
                    return true;
        return false;
    }
};

不出意外TLE了。
然后又想了想,用哈希,记录下每个数字出现的位置。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> map;
        int n = nums.size();
        for (int i=0; i<n; i++) {
            if (map.find(nums[i])!=map.end() && (i - map[nums[i]].back() <= k))
                return true;
            map[nums[i]].push_back(i);
        }
        return false;
    }
};

看了看答案,发现只要记录k个就可以了,里面有重复的就true。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int n = nums.size();
        for (int i=0; i<n; i++) {
            if (i > k)
                s.erase(nums[i-k-1]);
            if (s.find(nums[i]) != s.end())
                return true;
            s.insert(nums[i]);
        }
        return false;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容