当前位置: 面试刷题>> 查询区间 (经典算法题500道)


虽然原题目只给出了部分信息,但基于常见的面试算法题类型,我们可以假设这是一个关于“查询区间内满足特定条件的元素”的题目。这类题目常见于数据结构和算法中,特别是与线段树、树状数组、平衡二叉搜索树(如AVL树、红黑树)或有序数组等数据结构相关。

题目补充描述

题目:给定一个非负整数数组 nums 和一系列查询区间 [left, right],对于每个查询区间,请找出并返回该区间内所有元素的和。

示例

  • 输入:nums = [1, 3, 5, 7, 9, 11],查询区间 [[0, 2], [1, 5], [2, 2]]
  • 输出:[9, 25, 5]
    • 解释:第一个查询区间 [0, 2] 的元素和为 1 + 3 + 5 = 9
    • 第二个查询区间 [1, 5] 的元素和为 3 + 5 + 7 + 9 + 11 = 25
    • 第三个查询区间 [2, 2] 的元素和为 5

PHP 示例代码

function sumRange($nums, $queries) {
    $result = [];
    foreach ($queries as $query) {
        $left = $query[0];
        $right = $query[1];
        $sum = 0;
        for ($i = $left; $i <= $right; $i++) {
            $sum += $nums[$i];
        }
        $result[] = $sum;
    }
    return $result;
}

$nums = [1, 3, 5, 7, 9, 11];
$queries = [[0, 2], [1, 5], [2, 2]];
$result = sumRange($nums, $queries);
print_r($result);

Python 示例代码

def sumRange(nums, queries):
    result = []
    for left, right in queries:
        result.append(sum(nums[left:right+1]))
    return result

nums = [1, 3, 5, 7, 9, 11]
queries = [[0, 2], [1, 5], [2, 2]]
result = sumRange(nums, queries)
print(result)

JavaScript 示例代码

function sumRange(nums, queries) {
    const result = [];
    queries.forEach(([left, right]) => {
        let sum = 0;
        for (let i = left; i <= right; i++) {
            sum += nums[i];
        }
        result.push(sum);
    });
    return result;
}

const nums = [1, 3, 5, 7, 9, 11];
const queries = [[0, 2], [1, 5], [2, 2]];
const result = sumRange(nums, queries);
console.log(result);

以上代码示例均采用了最直接的方法,即对于每个查询区间,通过遍历数组并累加对应区间内的元素值来计算和。然而,对于大数据集和频繁查询的场景,这种方法可能效率较低。此时,可以考虑使用更高效的数据结构,如线段树或树状数组,来优化查询效率。

推荐面试题