当前位置: 面试刷题>> 和0 (经典算法题500道)


题目描述补充

给定一个整数数组,要求找到数组中所有子数组的和为零的子数组个数。注意,空数组不被计算在内,并且同一个子数组的不同起始位置应被视为不同的子数组。

示例

输入: [0, 5, -3, -1, 2, -3] 输出: 5

解释: 子数组的和为零的五个子数组分别为: [0], [5, -5], [3, -3], [1, -1, 0], [-1, 2, -3]

PHP 代码示例

function subarraySum($nums) {
    $count = 0;
    $prefixSum = array_fill(0, count($nums) + 1, 0); // 初始化前缀和数组,索引0处为0,便于计算
    $map = array(0 => 1); // 使用哈希表记录前缀和出现的次数

    $currentSum = 0;
    for ($i = 0; $i < count($nums); $i++) {
        $currentSum += $nums[$i];
        if (isset($map[$currentSum])) {
            // 如果当前前缀和已存在,说明从上一个相同前缀和到当前位置的子数组和为0
            $count += $map[$currentSum];
            $map[$currentSum]++; // 更新当前前缀和出现的次数
        } else {
            $map[$currentSum] = 1; // 首次出现该前缀和,记录次数为1
        }
    }

    return $count;
}

// 示例
$nums = [0, 5, -3, -1, 2, -3];
echo subarraySum($nums); // 输出: 5

Python 代码示例

def subarraySum(nums):
    count = 0
    prefix_sum = {0: 1}  # 初始化前缀和为0的次数为1
    current_sum = 0

    for num in nums:
        current_sum += num
        if current_sum in prefix_sum:
            count += prefix_sum[current_sum]  # 累加之前相同前缀和出现的次数
            prefix_sum[current_sum] += 1  # 更新当前前缀和出现的次数
        else:
            prefix_sum[current_sum] = 1  # 首次出现的前缀和

    return count

# 示例
nums = [0, 5, -3, -1, 2, -3]
print(subarraySum(nums))  # 输出: 5

JavaScript 代码示例

function subarraySum(nums) {
    let count = 0;
    const prefixSum = {0: 1}; // 初始化前缀和为0的次数为1
    let currentSum = 0;

    for (let num of nums) {
        currentSum += num;
        if (prefixSum[currentSum]) {
            count += prefixSum[currentSum]; // 累加之前相同前缀和出现的次数
            prefixSum[currentSum]++; // 更新当前前缀和出现的次数
        } else {
            prefixSum[currentSum] = 1; // 首次出现的前缀和
        }
    }

    return count;
}

// 示例
const nums = [0, 5, -3, -1, 2, -3];
console.log(subarraySum(nums)); // 输出: 5

码小课提示: 以上代码示例展示了如何在不同编程语言中解决这个算法问题。码小课网站上有更多关于算法和数据结构的精彩内容,欢迎大家前往学习交流!

推荐面试题