thảo luận Leetcode mỗi ngày

result += left * right
//4 * 4 = 16

class Solution {
    func numberOfSubarrays(_ nums: [Int], _ k: Int) -> Int {
        var result = 0

        var countOdd = 0
        var storeListEvens:[Int] = []
        var storeEven = 1
        for (index, value) in nums.enumerated() {
            if value%2 == 1 {
                countOdd += 1
               // Add storeEven in to list & reset counter
                storeListEvens.append(storeEven)
                storeEven = 1

               // Now we have enough k odds.
                if storeListEvens.count > k {
                    let left = storeListEvens.first!
                    let right = storeListEvens.last!
                    storeListEvens.removeFirst()
                    result += left * right
                    countOdd -= 1
                }
            } else {
                storeEven += 1
            }
        }

        if storeListEvens.count == k {
            let left = storeListEvens.first!
            let right = storeEven // List nums doesn't end by an odd, so the even count remain here.
            result += left * right
        }

        return result
    }
}

impl Solution {
    pub fn number_of_subarrays(nums: Vec<i32>, k: i32) -> i32 {
        let idx: Vec<_> = nums
            .iter()
            .enumerate()
            .filter_map(|(i, n)| (n % 2 != 0).then_some(i))
            .collect();

        let k = if k as usize > idx.len() {
            return 0;
        } else {
            k as usize
        };

        let lasti = idx.len() - k;
        return (0..=lasti).fold(0, |acc, i| {
            let l = if i == 0 {
                idx[i] + 1
            } else {
                idx[i] - idx[i - 1]
            };
            let h = if i < lasti { idx[i + k] } else { nums.len() } - idx[i + k - 1];
            acc + l * h
        }) as i32;
    }

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        map = {0: 1}
        sum = 0
        ans = 0
        for n in nums:
            sum += n % 2
            if map.get(sum - k):
                ans += map[sum-k]
            if map.get(sum):
                map[sum] += 1
            else:
                map[sum] = 1
        return ans

fun numberOfSubarrays(nums: IntArray, k: Int): Int {
        var oddCount = 0
        var prevIndex = 0
        var numSubarrayEndAtI = 0
        var total = 0
        for (num in nums) {
            if (num and 1 == 1) {
                oddCount++
                numSubarrayEndAtI = 0
            }
            while (oddCount == k) {
                oddCount -= nums[prevIndex++] and 1
                numSubarrayEndAtI++
            }
            total += numSubarrayEndAtI
        }
        return total
    }

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] % 2 == 0 ? 0 : 1;
        }

        Map<Integer, Integer> map = new HashMap<>();
        int curSum = 0;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            map.put(curSum, map.getOrDefault(curSum, 0) + 1);
            curSum += nums[i];

            ans += map.getOrDefault(curSum - k, 0);
        }

        return ans;
    }
}

object Solution {
  def numberOfSubarrays(nums: Array[Int], k: Int): Int = {
    val n = nums.length
    val transformedNums = nums.map(num => if (num % 2 == 0) 0 else 1)

    val prefixSumCount = scala.collection.mutable.Map[Int, Int]().withDefaultValue(0)
    var curSum = 0
    var ans = 0

    transformedNums.indices.foreach { i =>
      prefixSumCount(curSum) += 1
      curSum += transformedNums(i)
      ans += prefixSumCount(curSum - k)
    }

    ans
  }
}

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        vector<int> v;
        for(int num : nums){
            if(num % 2 == 1){
                v.emplace_back(1);
            }
            else{
                v.emplace_back(0);
            }
        }
        int preSum {0};
        int count {0};
        unordered_map<int,int> mpp;
        mpp[0] = 1;
        for(int i = 0; i < v.size(); i++){
            preSum += v[i];
            count += mpp[preSum - k];
            mpp[preSum]++;
        }

        return count;
    }
};

impl Solution {
    pub fn number_of_subarrays(nums: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        let (mut ps, mut pacc) = (vec![0; nums.len() + 1], 0usize);
        ps[0] = 1;

        return (0..nums.len()).fold(0, |sacc, i| {
            pacc += (nums[i] % 2) as usize;
            ps[pacc] += 1;

            if pacc >= k && ps[pacc - k] != 0 {
                sacc + ps[pacc - k]
            } else {
                sacc
            }
        });
    }
}

    public static int numberOfSubarrays(int[] nums, int k) {
        int count,res;
        int i;
        int first = curr = 0;
        int iRight = 1;
        int curr = 0;
        curLeft = curRight =count = res= 0;
        int[] left = new int[nums.length+1];
        int[] right = new int[nums.length+1];
        for(i=0; i<nums.length;i++){
            if(nums[i]%2==1){
                count++;
                if(count == 1)
                    first = i;
                left[count] = i-curr;
                curr = i;
            }
            if(count==k) {
                break;
            }
        }
        if(first ==0) left[1] = 1;
        else left[1]++;
        if(count!=k) return 0;
        i++;
        Arrays.fill(right, 1);
        for(int j =i; j<nums.length;j++){
            if(nums[j]%2==0) right[iRight]++;
            else {
                res+= left[iRight]*right[iRight];
                left[k+iRight]=right[iRight];
                iRight++;
            }
          }
        res+= left[iRight]*right[iRight];
        return res;
}