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


题目描述补充

给定一个整数数组 nums 和一个整数 k,编写一个函数来找到该数组中和为 k 的连续子数组的个数。换句话说,你需要找出数组中所有长度为 n 的连续子数组(其中 n 是不固定的),使得这些子数组中所有元素的和等于 k,并返回这样的子数组的总数。

示例 1:

输入: nums = [1,1,1], k = 2
输出: 2
解释: 子数组 [1,1] 和 [1,1] 的和均为 2,且它们在原数组中是连续的。

示例 2:

输入: nums = [1,2,3], k = 3
输出: 2
解释: 子数组 [1, 2] 和 [3] 的和均为 3,且它们在原数组中是连续的。

PHP 示例代码

function subarraySum($nums, $k) {
    $count = 0;
    $sum = 0;
    $prefixSum = array(0 => 1); // 初始化前缀和为0的计数为1,用于处理从数组开头就满足条件的子数组

    foreach ($nums as $num) {
        $sum += $num;
        if (isset($prefixSum[$sum - $k])) {
            $count += $prefixSum[$sum - $k];
        }
        if (!isset($prefixSum[$sum])) {
            $prefixSum[$sum] = 0;
        }
        $prefixSum[$sum]++;
    }

    return $count;
}

// 示例用法
$nums = [1,1,1];
$k = 2;
echo subarraySum($nums, $k); // 输出 2

Python 示例代码

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

    for num in nums:
        current_sum += num
        if current_sum - k in prefix_sum:
            count += prefix_sum[current_sum - k]
        if current_sum not in prefix_sum:
            prefix_sum[current_sum] = 0
        prefix_sum[current_sum] += 1

    return count

# 示例用法
nums = [1, 1, 1]
k = 2
print(subarraySum(nums, k))  # 输出 2

JavaScript 示例代码

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

    for (let num of nums) {
        currentSum += num;
        if (prefixSum[currentSum - k]) {
            count += prefixSum[currentSum - k];
        }
        if (!prefixSum[currentSum]) {
            prefixSum[currentSum] = 0;
        }
        prefixSum[currentSum]++;
    }

    return count;
}

// 示例用法
let nums = [1, 1, 1];
let k = 2;
console.log(subarraySum(nums, k)); // 输出 2

码小课: 以上代码展示了如何在 PHP、Python 和 JavaScript 中解决“k数和”问题。每种语言的实现都利用了哈希表(或字典)来记录前缀和的出现次数,以便在遍历数组时快速判断是否存在某个前缀和使得当前前缀和与它的差等于 k。这种方法的时间复杂度为 O(n),其中 n 是数组的长度。码小课网站上有更多关于算法和数据结构的精彩内容,欢迎大家前去学习交流!