区间和的个数 (经典算法题500道),程序员经典面试笔试题目, 码小课

当前位置：面试刷题>> 区间和的个数 (经典算法题500道)

题目描述补充

题目：区间和的个数

给定一个整数数组 nums 和一个整数 target，求该数组中所有可能的非空子数组（子序列的连续部分）的和等于 target 的个数。

示例：

输入: nums = [1, 1, 2, 2, 2, 1], target = 5
输出: 4
解释:
有四种组合方式的子数组和为 5：
[1, 1, 2, 2]
[1, 2, 2, 1]
[1, 2, 2]
[2, 2, 1]

解题思路

为了解决这个问题，我们可以使用前缀和加哈希表的方法。首先，我们计算数组的前缀和，并使用哈希表（在PHP中为关联数组，Python和JavaScript中为对象或Map）来记录每个前缀和出现的次数。遍历数组时，我们可以利用当前的前缀和和之前某个前缀和的差来判断是否存在和为target的子数组。

PHP 示例代码

function subarraySum($nums, $target) {
    $count = 0;
    $prefixSum = 0;
    $prefixSumCounts = array(0 => 1); // 初始化前缀和为0的计数为1，用于处理前缀和自身相减等于target的情况

    foreach ($nums as $num) {
        $prefixSum += $num;
        $complement = $prefixSum - $target;

        if (isset($prefixSumCounts[$complement])) {
            $count += $prefixSumCounts[$complement];
        }

        if (!isset($prefixSumCounts[$prefixSum])) {
            $prefixSumCounts[$prefixSum] = 0;
        }
        $prefixSumCounts[$prefixSum]++;
    }

    return $count;
}

// 示例
$nums = [1, 1, 2, 2, 2, 1];
$target = 5;
echo subarraySum($nums, $target); // 输出 4

Python 示例代码

def subarraySum(nums, target):
    count = 0
    prefix_sum = 0
    prefix_sum_counts = {0: 1}

    for num in nums:
        prefix_sum += num
        complement = prefix_sum - target

        if complement in prefix_sum_counts:
            count += prefix_sum_counts[complement]

        prefix_sum_counts[prefix_sum] = prefix_sum_counts.get(prefix_sum, 0) + 1

    return count

# 示例
nums = [1, 1, 2, 2, 2, 1]
target = 5
print(subarraySum(nums, target))  # 输出 4

JavaScript 示例代码

function subarraySum(nums, target) {
    let count = 0;
    let prefixSum = 0;
    let prefixSumCounts = {0: 1};

    for (let num of nums) {
        prefixSum += num;
        const complement = prefixSum - target;

        if (prefixSumCounts[complement]) {
            count += prefixSumCounts[complement];
        }

        if (!prefixSumCounts[prefixSum]) {
            prefixSumCounts[prefixSum] = 0;
        }
        prefixSumCounts[prefixSum]++;
    }

    return count;
}

// 示例
const nums = [1, 1, 2, 2, 2, 1];
const target = 5;
console.log(subarraySum(nums, target)); // 输出 4

码小课提示