1248. Count Number of Nice Subarrays

leetcode medium

#array#csharp#leetcode#medium#sliding-window#string#two-pointers

Task

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

Input: arr = [1,2]

Output: 2

C# solution

matched/original

public class Solution {
    public int NumberOfSubarrays(int[] nums, int k) {
        return AtMost(nums, k) - AtMost(nums, k - 1);
    }
    private int AtMost(int[] nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumberOfSubarrays(vector<int>& nums, int k) {
        return AtMost(nums, k) - AtMost(nums, k - 1);
    }
    private int AtMost(vector<int>& nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
}

Java solution

matched/original

public class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
}

JavaScript solution

matched/original

var numberOfSubarrays = function(nums, k) {
    return atMost(nums, k) - atMost(nums, k - 1);
};

function atMost(nums, k) {
    let res = 0, left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] % 2 === 1) count++;
        while (count > k) {
            if (nums[left++] % 2 === 1) count--;
        }
        res += right - left + 1;
    }
    return res;
}

Python solution

matched/original

def numberOfSubarrays(nums, k):
    def atMost(nums, k):
        count = 0
        left = 0
        res = 0
        for right in range(len(nums)):
            if nums[right] % 2 == 1:
                count += 1
            while count > k:
                if nums[left] % 2 == 1:
                    count -= 1
                left += 1
            res += right - left + 1
        return res
    return atMost(nums, k) - atMost(nums, k - 1)

Go solution

matched/original

func numberOfSubarrays(nums []int, k int) int {
    return atMost(nums, k) - atMost(nums, k-1)
}

func atMost(nums []int, k int) int {
    res, left, count := 0, 0, 0
    for right := 0; right < len(nums); right++ {
        if nums[right] % 2 == 1 {
            count++
        }
        for count > k {
            if nums[left] % 2 == 1 {
                count--
            }
            left++
        }
        res += right - left + 1
    }
    return res
}

Explanation

Algorithm

Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.

Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.

Подсчитайте количество таких подмассивов и верните этот результат.

😎