サブリストを削除して、C++でkの上下に同じ数の要素を取得するプログラム

numsと呼ばれる番号のリストと別の番号kがあるとすると、リストからサブリストを最大1回削除できます。結果として得られる最長のリストの長さを、厳密にkより小さく厳密にkより大きい数の量が同じになるように見つける必要があります。

したがって、入力がnums =[6、10、8、9、3、5]、k =6の場合、サブリスト[9]を削除した場合と同様に、出力は5になり、[6、 10、8、3、5]であり、6よりも小さい2つの数値[3、5]と6よりも大きい2つの数値[10、8]があります。

これを解決するには、次の手順に従います-

• nums + 1と同じサイズの配列vを定義し、0で埋めます
• cnt：=0
• iを初期化する場合：=0、i
• nums [i]
• （cntを1増やします）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int solve(vector<int>& nums, int k) {
      vector<int> v(nums.size() + 1, 0);
      int cnt = 0;
      for (int i = 0; i < nums.size(); ++i) {
         if (nums[i] < k)
            ++cnt;
         else if (nums[i] > k)
            --cnt;
         v[i + 1] = cnt;
      }
      if (v.back() == 0) return int(nums.size());
      int delta = v.back();
      map<int, int> m;
      int ans = INT_MAX;
      for (int i = 1; i <= v.size(); ++i) {
         if (m[v[i] - v.back()] != 0 || v[i] - v.back() == 0) {
            ans = min(ans, i - m[v[i] - v.back()]);
         }
         m[v[i]] = i;
      }
      if (ans == INT_MAX)
         return 0;
      else
         return int(nums.size() - ans);
   }
};
main(){
   Solution ob;
   vector<int> v = {6, 10, 8, 9, 3, 5};
   int k = 6;
   cout << ob.solve(v, k); }

入力

{6, 10, 8, 9, 3, 5}, 6

出力

5