【Day 38】 前缀和专题

题目描述

1. 网易面试题

有一个班级有 n 个人，给出 n 个元素，第 i 个元素代表 第 i 位同学的考试成绩，接下进行 m 次询问，每次询问给出一个数值 t ，表示第 t 个同学，然后需要我们输出第 t 个同学的成绩超过班级百分之几的人，百分数 p 可以这样算：p = (不超过第 t 个同学分数的人数 ) / n * 100%。输出的时候保留到小数点后 6 位，并且需要四舍五入。

输入描述：第一行输入两个数 n 和 m，两个数以空格隔开，表示 n 个同学和 m 次询问。第二行输入 n 个数值 ni，表示每个同学的分数，第三行输入 m 个数值mi，表示每次询问是询问第几个同学。（注意，这里 2<=n，m<=100000，0<=ni<=150，1<=mi<=n）

输出描述：输出 m 行，每一行输出一个百分数 p，代表超过班级百分之几的人。

示例1：

输入 ：

3 2

50 60 70

1 2

输出

33.333333%

66.666667%

1. 1371. 每个元音包含偶数次的最长子字符串
2. 560. 和为 K 的子数组

其他：

• 308
• 525
• 1139
• 1176
• 1182
• 1277
• 1292
• 1314
• 1504

我的回答

解法一

时空复杂度

var subarraySum = function (nums, k) {
    let count = 0
    for (let i = 0; i < nums.length; i++) {
        let sum = 0
        for (let j = i; j < nums.length; j++) {
            sum += nums[j]
            if (sum == k) count++
        }
    }
    return count
};

解法二

var subarraySum = function (nums, k) {
    const hashmap = {};
    let acc = 0;
    let count = 0;
 
    for (let i = 0; i < nums.length; i++) {
        acc += nums[i]
        if (acc == k) count++
        if (hashmap[acc - k]) count += hashmap[acc - k]
        hashmap[acc] = hashmap[acc] ? hashmap[acc] + 1 : 1
    }
    return count;
};

参考回答

• 官方题解
• 精选题解