讨论一个问题来回答对给定数组的查询。例如，对于每个查询索引，我们需要查找索引左侧的 1 和 0 的数量。
Input: arr[ ] = { 0, 1, 1, 1, 0, 0, 0, 1, 0, 0}, queries[ ] = { 2, 4, 1, 0, 5 }
Output:
query 1: zeros = 1,ones = 1
query 2: zeros = 1,ones = 3
query 3: zeros = 1,ones = 0
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3
Input: arr[ ] = { 0, 0, 1, 1, 1, 0, 1, 0, 0, 1 }, queries[ ] = { 3, 2, 6 }
Output:
query 1: zeros = 2,ones = 1
query 2: zeros = 2,ones = 0
query 3: zeros = 3,ones = 3
登录后复制
寻找解决方案的方法
天真的方法
解决这个问题的简单方法是遍历数组到查询的索引并检查每个元素；如果为 0，则将零计数器加 1，否则将个计数器加 1。
示例
#include
using namespace std;
int main(){
int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
int queries[] = { 2, 4, 1, 0, 5 };
int qsize = sizeof(queries) / sizeof(queries[0]);
int zeros=0,ones=0;
// loop for running each query.
for(int i = 0;i
