Leetcode 219. 存在重复元素

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

C++解法

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
class Solution {
public:
    static bool comparator(pair<int, int> & lhs, pair<int, int> & rhs) { return lhs.second < rhs.second; }
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        vector<pair<int, int>> items;
        for (int i = 0; i < nums.size(); ++i) items.push_back({i, nums[i]});
        sort(items.begin(), items.end(), comparator);
        int n = (int)items.size();
        for(int i = 1; i < n; ++i) {
            if (items[i].second == items[i - 1].second && abs(items[i].first - items[i - 1].first) <= k) return true;
        }
        return false;
    }
};
int main(int argc, const char * argv[]) {
    Solution solution;
    vector<int> items {1, 2, 3, 1};
    int k = 3;
    cout << solution.containsNearbyDuplicate(items, k) << endl;
    items = {1, 0, 1, 1};
    k = 1;
    cout << solution.containsNearbyDuplicate(items, k) << endl;
    items = {1, 2, 3, 1, 2, 3};
    k = 2;
    cout << solution.containsNearbyDuplicate(items, k) << endl;
    return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。