当前位置： 面试刷题>> 移除k位 (经典算法题500道)
**题目描述补充**：
题目：给定一个非负整数数组 `nums` 和一个整数 `k`，你需要找到该数组中和为 `k` 的子数组的个数。子数组是数组中元素的连续非空序列。
**示例 1**:
```
输入: nums = [1,1,1], k = 2
输出: 2
解释: 子数组 [1,1] 和 [1,1] 的和均为 2，且它们都是长度为 2 的连续子数组。
```
**示例 2**:
```
输入: nums = [1,2,3], k = 3
输出: 2
解释: 子数组 [1, 2] 和 [3] 的和均为 3，且它们都是长度为 1 或 2 的连续子数组。
```
**解题思路**：
这个问题可以使用前缀和（Prefix Sum）结合哈希表（Hash Table）来解决。我们遍历数组，同时计算当前位置之前的所有元素的和（前缀和），并存储在哈希表中。每当我们计算出一个新的前缀和时，我们检查哈希表中是否已经存在一个前缀和，使得两者之差为 `k`。如果存在，则意味着从该前缀和对应的位置到当前位置之间的子数组和就是 `k`。
**PHP 示例代码**：
```php
function subarraySum($nums, $k) {
$count = 0;
$sum = 0;
$prefixSum = array(0 => 1); // 初始化前缀和为0的计数为1，用于处理数组开始即为k的情况
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 示例代码**：
```python
def subarraySum(nums, k):
count = 0
prefix_sum = 0
prefix_count = {0: 1} # 初始化前缀和为0的计数为1
for num in nums:
prefix_sum += num
if prefix_sum - k in prefix_count:
count += prefix_count[prefix_sum - k]
if prefix_sum not in prefix_count:
prefix_count[prefix_sum] = 0
prefix_count[prefix_sum] += 1
return count
# 示例测试
nums = [1,1,1]
k = 2
print(subarraySum(nums, k)) # 输出: 2
```
**JavaScript 示例代码**：
```javascript
function subarraySum(nums, k) {
let count = 0;
let prefixSum = 0;
let prefixCount = {0: 1}; // 初始化前缀和为0的计数为1
for (let num of nums) {
prefixSum += num;
if (prefixCount[prefixSum - k]) {
count += prefixCount[prefixSum - k];
}
if (!prefixCount[prefixSum]) {
prefixCount[prefixSum] = 0;
}
prefixCount[prefixSum]++;
}
return count;
}
// 示例测试
const nums = [1,1,1];
const k = 2;
console.log(subarraySum(nums, k)); // 输出: 2
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖算法设计、数据结构、面试技巧等多个方面，帮助大家提升编程技能。