ACWING 570. 气球游戏（DAY 311）---- 腾讯后端面试题

• • 原题题目
  • 代码实现（首刷自解）

#include 
#include 
#include 
#include 

using namespace std;

int main() {
  int shottimes, bubbles;
  cin >> shottimes >> bubbles;
  
  vector used(bubbles + 1, 1);
  vector shots;
  unordered_set remainbubbles;
  int bubble = 0;
  for (int i = 0; i < shottimes; ++i) {
    cin >> bubble;
    shots.emplace_back(bubble);
  }
  for (int i = 1; i <= bubbles; ++i) {
    remainbubbles.emplace(i);
  }
  
  int left = 0, right = 0, shotssize = shots.size();
  int ans = INT_MAX;
  while (right < shotssize) {
    while (right < shotssize && !remainbubbles.empty()) {
      bubble = shots[right++];
      if (bubble == 0) continue;
      --used[bubble];
      if (!used[bubble]) remainbubbles.erase(remainbubbles.find(bubble));
    }
    if (remainbubbles.empty()) ans = min(ans, right - left);
    
    while (left < right && remainbubbles.empty()) {
      ans = min(ans, right - left);
      bubble = shots[left++];
      if (bubble == 0) continue;
      ++used[bubble];
      if (used[bubble] >= 1) remainbubbles.emplace(bubble);
    }
  }
  
  ans = ans == INT_MAX ? -1 : ans;
  cout << ans;
  return 0;
}