前缀和算法：蜡烛之间的盘子 💿

蜡烛之间的盘子

题目地址： https://leetcode-cn.com/problems/plates-between-candles/

题目描述：

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 ‘’ 和 ‘|’ ，其中 '’ 表示一个 盘子 ，’|’ 表示一支 蜡烛 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] 表示 子字符串 s[lefti…righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。

比方说，s = “|||||" ，查询 [3, 8] ，表示的是子字符串 "||**|” 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。
请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例

输入：s = "**|**|***|", queries = [[2,5],[5,9]]
输出：[2,3]
解释：
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。

输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
输出：[9,0,0,0,0]
解释：
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。

题目分析

这道题目其实难度完全在于算法复杂度上面，一开始我编写的代码时间复杂度是O(n^2)，结果没有通过测试用例（这个测试用例太长了），然后去翻看题解，发现居然还有前缀和这种方式进行求解，学到了学到了。

PS:这里我先说一下错误的代码

这里需要获取截取的子字符串中符合要求的盘子数量，那么肯定要先进行截取，并且由于参数是一个截取的二维数组，所以必须要一个for循环。

在这里我定义了一个countNums方法，用来处理截取到的字符串片段。
在此方法中，首先获取’|‘第一个和最后一个的index，然后通过左右两端指针的方式，逐步向内进行判断’*'盘子的数量

function countNums(str) {
    let arr = str.split(""), count = 0, first = str.indexOf('|'), last = str.lastIndexOf('|');
    if (first == last || first + 1 == last) return 0;
    let i = first + 1, j = last - 1;
    while(i < j + 1) {
        if (i == j && arr[i] == '*') {
            count++;
        } else {
            if (arr[i] == '*') { count++; }
            if (arr[j] == '*') { count++; }
        }
        i++; j--;
    }
    return count;
}
// current结果数组
let currentAns = [];
for(let item of queries) { 
    currentAns.push( countNums(s.slice(item[0], item[1] + 1)) ) 
}

但是这样就会需要用到两次循环进行判断，非常的耗时。所以虽然能够求到最终的结果，但是并不符合时间要求。

前缀和方式： 将字符串变成数组，并创建一个新的盘子数量数组。在盘子数组中，每一个元素是前面所有的盘子数量，如果是‘|’。那么就与之前格子中的盘子数量相同。这样就不需要多一次的循环了

代码

var platesBetweenCandles = function(s, queries) {
    let currentAns = [];
    // 预处理 创建一个盘子数组，数组中显示当前位置盘子的总数
    let plateArr = [], sArr = s.split(''), pNums = 0;
    for(let i of sArr) {
        if (i == '*') {
            pNums++;
        }
        plateArr.push(pNums)
    }
    
    for(let item of queries) {
        let str = s.slice(item[0], item[1] + 1);
        let first = str.indexOf('|'), last = str.lastIndexOf('|');
        if (first == -1) {
            currentAns.push(0)
        } else {
            currentAns.push( plateArr[item[0] + last] - plateArr[item[0] + first] );
        }
    }
    return currentAns;
};