Line data    Source code

       1              : // Copyright (c) 2022 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : // Created: 2022/01/19 10:53
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include <unordered_set>
      21              : #include <vector>
      22              : 
      23              : namespace {
      24              : class Solution {
      25              : public:
      26            3 :     bool containsNearbyDuplicate(const std::vector<int>& nums, int k) {
      27            3 :         std::unordered_set<int> set;
      28           15 :         for (int i = 0; i < nums.size(); ++i) {
      29           14 :             if (set.size() > k) {
      30            5 :                 set.erase(nums[i - k - 1]);
      31              :             }
      32           14 :             if (set.count(nums[i]) > 0) {
      33            2 :                 return true;
      34              :             }
      35           12 :             set.emplace(nums[i]);
      36              :         }
      37            1 :         return false;
      38            3 :     }
      39              : };
      40              : } // namespace
      41              : 
      42            4 : TEST(Leetcode, contains_duplicate_ii) {
      43            1 :     Solution s;
      44              :     {
      45            1 :         std::vector<int> nums = {1, 2, 3, 1};
      46            1 :         EXPECT_TRUE(s.containsNearbyDuplicate(nums, 3));
      47            1 :     }
      48              :     {
      49            1 :         std::vector<int> nums = {1, 0, 1, 1};
      50            1 :         EXPECT_TRUE(s.containsNearbyDuplicate(nums, 1));
      51            1 :     }
      52              :     {
      53            1 :         std::vector<int> nums = {1, 2, 3, 1, 2, 3};
      54            1 :         EXPECT_FALSE(s.containsNearbyDuplicate(nums, 2));
      55            1 :     }
      56            1 : }