Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 3737. Count Subarrays With Majority Element I

---

題目：


解答1：

class Solution {
public:
    int countMajoritySubarrays(vector<int>& nums, int target) {
        int ans = 0;
        int n = nums.size();

        for (int i = 0; i < n; ++i) {
            int no = 0;
            int yes = 0;

            for (int j = i; j < n; ++j) {
                if (nums[j] == target) {
                    yes += 1;
                }
                else {
                    no += 1;
                }

                if (yes > no) {
                    ans += 1;
                }
            }
        }

        return ans;
    }
};

解答2：

class Solution {
public:
    int countMajoritySubarrays(vector<int>& nums, int target) {
        int ans = 0;
        int pref = 0;
        unordered_map<int, long> mp;

        mp[0] = 1;

        for (int n : nums) {
            if (n == target) {
                pref += 1;
            }
            else {
                pref -= 1;
            }

            for (auto& [k, v] : mp) {
                if (k < pref) {
                    ans += v;
                }
            }

            mp[pref] += 1;
        }

        return ans;
    }
};