php 解法, 执行用时: 192 ms, 内存消耗: 31 MB, 提交时间: 2023-10-21 20:35:02

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function evenProduct($nums) {
        // 一个重要的性质是： 只有奇数*奇数 才是奇数，否则都是偶数
        // 如果位置i是偶数，那以其结尾的都是偶数
        // 否则，以其结尾的偶数个数 = 前一个位置作为结尾的偶数个数
        $result = 0;

        // 当前位置结尾的偶数积个数
        $now = 0;
        $n = count($nums);
        for ($i = 0; $i < $n; $i++) {
            if ($nums[$i] & 1) { // 奇数，与前一个相同
                
            } else { // 偶数，与前面所有组合都可以
                $now = $i + 1;
            }
            
            $result += $now;
        }
        
        return $result;
    }
}

rust 解法, 执行用时: 8 ms, 内存消耗: 3.3 MB, 提交时间: 2023-10-21 20:34:45

impl Solution {
    pub fn even_product(nums: Vec<i32>) -> i64 {
        let mut ans = 0;
        let mut cnt = 0;
        let n = nums.len();

        for i in 0..n {
            if nums[i] & 1 == 0 {
                cnt = i as i64  + 1;
            }

            ans += cnt;
        }

        ans
    }
}

java 解法, 执行用时: 4 ms, 内存消耗: 57.7 MB, 提交时间: 2023-10-21 20:34:22

class Solution {
    public long evenProduct(int[] nums) {
        int left = -1;
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 偶数匹配所有值，并刷新左端点
            if (nums[i] % 2 == 0) {
                sum += i + 1;
                left = i;
            }
            // 奇数找到最近的偶数进行配对，加入最近偶数之前的所有值
            else {
                sum += left + 1;
            }
        }
        return sum;
    }
}

python3 解法, 执行用时: 84 ms, 内存消耗: 27.5 MB, 提交时间: 2023-10-21 20:34:07

class Solution:
    def evenProduct(self, nums: List[int]) -> int:
        ans,lst,n = 0,-1,len(nums)
        for i in range(n):
            if not nums[i] & 1:
                lst = i
            ans += lst + 1
        return ans
        
    def evenProduct2(self, nums: List[int]) -> int:
        # 定义状态表示数组dp, 其中的元素为一个二元组
        # dp[i][0]表示以nums[i]结尾的乘积为偶数的数组数量
        # dp[i][1]表示以nums[i]结尾的乘积为奇数的数组数量
        # 若当前nums[i]为奇数，则可以与nums[i - 1]结尾的乘积为偶数的数组组合
        # 所以dp[i][0] = dp[i - 1][0], dp[i][1] = dp[i - 1] + 1(可以和nums[i - 1]结尾的组合成乘积为奇数的数组，包括自己)
        
        # nums[i]为偶数时, 则可以和以nums[i - 1]结尾的任何数组组合为乘积为偶数的数组
        # dp[i][0] = i + 1 (包括自己)
        # 无法组合成乘积为奇数的数组 dp[i][1] = 0

        # 每个dp[i]都只依赖与dp[i - 1]，所以可以使用滚动数组优化
        a = b = ans = 0
        for i, n in enumerate(nums, start = 1):
            if n & 1:
                b += 1
            else:
                a = i
                b = 0
            ans += a
        
        return ans