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


题目描述补充

题目:子数组求和

给定一个整数数组 nums 和一个目标值 k,请找出该数组中所有和为 k 的连续子数组(至少包含一个元素)。

注意

  • 你可以按任何顺序返回答案。
  • 子数组的长度至少为 1。

示例 1:

输入: nums = [1, -1, 5, -2, 3], k = 3
输出: [[1, -1, 5], [-2, 3]]

示例 2:

输入: nums = [1], k = 1
输出: [[1]]

PHP 代码示例

function subarraySum($nums, $k) {
    $result = [];
    $prefixSum = [];
    $prefixSum[0] = 0;
    $currentSum = 0;
    
    for ($i = 0; $i < count($nums); $i++) {
        $currentSum += $nums[$i];
        
        if (isset($prefixSum[$currentSum - $k])) {
            foreach (range($prefixSum[$currentSum - $k] + 1, $i) as $j) {
                $result[] = array_slice($nums, $j, $i - $j + 1);
            }
        }
        
        if (!isset($prefixSum[$currentSum])) {
            $prefixSum[$currentSum] = $i;
        }
    }
    
    return $result;
}

// 示例用法
$nums = [1, -1, 5, -2, 3];
$k = 3;
$result = subarraySum($nums, $k);
print_r($result);

注意:上述 PHP 示例代码可能不完全符合题目要求,因为它在处理重叠子数组时会产生重复结果,并且没有优化以避免重复计算。这里主要是为了展示一个基本的解题思路。

Python 代码示例

def subarraySum(nums, k):
    result = []
    current_sum = 0
    prefix_sum = {0: -1}  # 使用字典来存储前缀和及其对应的索引,-1 是为了处理从数组开始的情况
    
    for i, num in enumerate(nums):
        current_sum += num
        if current_sum - k in prefix_sum:
            start = prefix_sum[current_sum - k] + 1
            result.append(nums[start:i+1])
        if current_sum not in prefix_sum:
            prefix_sum[current_sum] = i
    
    return result

# 示例用法
nums = [1, -1, 5, -2, 3]
k = 3
print(subarraySum(nums, k))

JavaScript 代码示例

function subarraySum(nums, k) {
    const result = [];
    let currentSum = 0;
    const prefixSum = { 0: -1 }; // 使用对象来存储前缀和及其对应的索引,-1 是为了处理从数组开始的情况
    
    for (let i = 0; i < nums.length; i++) {
        currentSum += nums[i];
        if (prefixSum[currentSum - k] !== undefined) {
            const start = prefixSum[currentSum - k] + 1;
            result.push(nums.slice(start, i + 1));
        }
        if (!prefixSum[currentSum]) {
            prefixSum[currentSum] = i;
        }
    }
    
    return result;
}

// 示例用法
const nums = [1, -1, 5, -2, 3];
const k = 3;
console.log(subarraySum(nums, k));

以上代码均提供了解决“子数组求和”问题的不同语言实现。码小课网站中有更多相关内容分享给大家学习,可以帮助深入理解算法和数据结构。

推荐面试题