3739. Count Subarrays With Majority Element II Hard

1/**
2 * [3739] Count Subarrays With Majority Element II
3 *
4 * You are given an integer array nums and an integer target.
5 * Return the number of <span data-keyword="subarray-nonempty">subarrays</span> of nums in which target is the majority element.
6 * The majority element of a subarray is the element that appears strictly more than half of the times in that subarray.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">nums = [1,2,2,3], target = 2</span>
11 * Output: <span class="example-io">5</span>
12 * Explanation:
13 * Valid subarrays with target = 2 as the majority element:
14 * 
15 * 	nums[1..1] = [2]
16 * 	nums[2..2] = [2]
17 * 	nums[1..2] = [2,2]
18 * 	nums[0..2] = [1,2,2]
19 * 	nums[1..3] = [2,2,3]
20 * 
21 * So there are 5 such subarrays.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">nums = [1,1,1,1], target = 1</span>
26 * Output: <span class="example-io">10</span>
27 * Explanation: 
28 * ​​​​​​​All 10 subarrays have 1 as the majority element.
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">nums = [1,2,3], target = 4</span>
33 * Output: <span class="example-io">0</span>
34 * Explanation:
35 * target = 4 does not appear in nums at all. Therefore, there cannot be any subarray where 4 is the majority element. Hence the answer is 0.
36 * </div>
37 *  
38 * Constraints:
39 * 
40 * 	1 <= nums.length <= 10^​​​​​​​5
41 * 	1 <= nums[i] <= 10^​​​​​​​9
42 * 	1 <= target <= 10^9
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/count-subarrays-with-majority-element-ii/
48// discuss: https://leetcode.com/problems/count-subarrays-with-majority-element-ii/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn count_majority_subarrays(nums: Vec<i32>, target: i32) -> i64 {
54        
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_3739() {
66    }
67}
68