题目描述

给定一个整数数组 nums 和一个目标值 k，请找出该数组中所有和为 k 的连续子数组，并返回这些子数组的起始与结束索引（包含）。数组的下标从 0 开始。

示例 1:

输入: nums = [1,2,3], k = 3
输出: [[0,2]]
解释: 只有一个子数组 [1, 2, 3] 的和为 3，其起始和结束索引为 [0, 2]。

示例 2:

输入: nums = [1,-1,0], k = 0
输出: [[0,1], [1,2], [0,2]]
解释: 子数组 [1, -1]、[-1, 0] 和 [1, -1, 0] 的和都为 0。

PHP 示例代码

function subarraySum($nums, $k) {
    $result = [];
    $sum = 0;
    $prefixSum = [];
    $prefixSum[0] = -1; // 初始化前缀和为0的索引为-1，用于处理从数组开头开始的子数组

    for ($i = 0; $i < count($nums); $i++) {
        $sum += $nums[$i];
        if (isset($prefixSum[$sum - $k])) {
            // 如果之前有过相同的前缀和，则当前位置与那个位置的索引差即为子数组的起始和结束索引
            foreach ($prefixSum[$sum - $k] as $prevIndex) {
                $result[] = [$prevIndex + 1, $i];
            }
        }
        if (!isset($prefixSum[$sum])) {
            $prefixSum[$sum] = [];
        }
        $prefixSum[$sum][] = $i; // 记录当前位置作为某个前缀和的索引
    }

    return $result;
}

// 示例
$nums = [1, -1, 0];
$k = 0;
print_r(subarraySum($nums, $k));

Python 示例代码

def subarraySum(nums, k):
    result = []
    current_sum = 0
    prefix_sum = {0: -1}  # 初始化前缀和为0的索引为-1

    for i, num in enumerate(nums):
        current_sum += num
        if current_sum - k in prefix_sum:
            result.append([prefix_sum[current_sum - k] + 1, i])
        if current_sum not in prefix_sum:
            prefix_sum[current_sum] = i

    return result

# 示例
nums = [1, -1, 0]
k = 0
print(subarraySum(nums, k))

JavaScript 示例代码

function subarraySum(nums, k) {
    const result = [];
    let currentSum = 0;
    const prefixSum = { 0: -1 }; // 初始化前缀和为0的索引为-1

    for (let i = 0; i < nums.length; i++) {
        currentSum += nums[i];
        if (prefixSum[currentSum - k] !== undefined) {
            // 如果存在相同的前缀和，则添加起始和结束索引
            for (const prevIndex of prefixSum[currentSum - k]) {
                result.push([prevIndex + 1, i]);
            }
        }
        if (prefixSum[currentSum] === undefined) {
            prefixSum[currentSum] = [];
        }
        prefixSum[currentSum].push(i); // 记录当前位置
    }

    return result;
}

// 示例
const nums = [1, -1, 0];
const k = 0;
console.log(subarraySum(nums, k));

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法基础、数据结构、面试题解析等，帮助大家提升编程能力。