219 存在重复元素 II

本文最后更新于：2021年2月5日 晚上

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]**，并且 i 和 j 的差的 **绝对值 至多为 k。

示例 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

Solution

  • 暴力解法，超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// @lc code=start
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        for(int i=0; i<nums.size()-1; ++i){
            for(int j=i+1; j<=i+k && j<nums.size(); ++j){
                if(nums[i]==nums[j])
                    return true;
            }
        }
        return false;
    }
};
// @lc code=end
  • 滑动窗口法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size()<=1 || k<=0)
            return false;
        unordered_set<int> record;
        for(int i=0; i<nums.size(); ++i){
            if(record.find(nums[i]) != record.end())
                return true;
            record.insert(nums[i]);
            if(record.size()==k+1)
                record.erase(nums[i-k]);
        }
        return false;
    }
};
  • 利用哈希表存储元素对应的所有位置下标 map {num, pos}
  • 然后遍历元素的所有下标，找到是否有距离小于 k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// @lc code=start
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> record;
        for (int i = 0; i < nums.size(); ++i) {
            record[nums[i]].push_back(i);
        }
        for (auto iter = record.begin(); iter != record.end(); ++iter){
            if (iter->second.size() > 1) {
                vector<int> temp = iter->second;
                int res = nums.size() + 1;
                for (int i = 0; i < temp.size(); ++i) {
                    for (int j = i + 1; j < temp.size(); ++j) {
                        res = min(res, temp[j] - temp[i]);
                        if (res <= k) return true;
                    }
                }
            }
        }
        return false;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！