这里有一个来自hackerbank的问题，我有一个解决方案，但由于超过了时间限制，有些测试用例失败了。我不知道更好的解决方案。
查找子阵列中元素的和(如果子阵列中有0，Sum=Sum+number x(
输入：数字：主阵列(1索引(
查询：
array of query: left index, right index, number x(0-indexed)
输出：
与查询相对应的和数组。
我的C++代码解决方案：
vector<long> findSum(vector<int>numbers, vector<vector<int>> queries)
{
vector<long>result;
long sum = 0;
int count = 0;
for(auto i : queries)
{
sum = 0;
count = 0;
int l = i[0] - 1;
int r = i[1]-1;
int x = i[2];
for(int j =l; j<r;j++)
{
sum+=numbers[j]==0?x:numbers[j];
}
result.push_back(sum);
}
return result;
}
根据@Annity的建议，您需要维护两个数组：
- 迄今为止所有数字的总和。在索引的任何一点，它都应该是以前所有数字的总和
- 与上面相同，但它应该有所有以前零的总计数
您应该避免嵌套循环以降低时间复杂性。以下是javascript中的解决方案：
function findSum(numbers, queries) {
let result = [];
let subArraySum = [];
let countZero = numbers[0] == 0 ? 1 : 0;
let zeroArr = [];
zeroArr[0] = countZero;
subArraySum[0] = numbers[0];
for (let i = 1; i <= numbers.length - 1; i++) {
if (numbers[i] == 0) {
countZero++;
zeroArr[i] = countZero;
}
else {
zeroArr[i] = countZero;
}
subArraySum[i] = subArraySum[i - 1] + numbers[i];
}
for (let q of queries) {
if (q.length == 3) {
let i = q[0];
let j = q[1];
let x = q[2];
let sum = 0;
sum = subArraySum[j - 1] - ((i - 2 < 0 ) ? 0 : subArraySum[i - 2]);
sum = sum + (zeroArr[j - 1] - ((i - 2 < 0 ) ? 0 : zeroArr[i - 2])) * x;
result.push(sum);
}
}
return result;
}
console.log(findSum([5, 10, 15], [
[1, 2, 5]
]))
console.log(findSum([0, 10, 15], [
[1, 2, 5]
]))这是我想到的解决方案。
您需要创建两个新数组——一个用于求和，一个用于零的数量。例如CCD_ 1和CCD_。
在这两个数组中，您将存储从第一个元素到当前元素的和值和零数。事情就是这样发展的：
循环所有的数字。
对于索引为i的每个数字，在sums[i]中保存从第一个元素到当前元素的所有元素的累积和，而在zeroes[i]中保存第一个元素至当前元素的零数。
然后循环所有查询。
对于每个查询，计算总和：
从sums数组中获取具有右索引的元素的sum，并减去左索引之前的元素的和。(sum = sums[r] - sums[l-1](
如果从右索引上的元素中的数字减去左索引前元素中的零计数，则会得到区间中的零数。(zero = zeroes[r] - zeroes[l-1](
然后将其与查询中的第三个元素相乘，并将其添加到总和中。
这就是查询的总和。
这是在python 中
tempRes=0
temp = []
for b in range(len(queries)):
for k in range(queries[b][0]-1,queries[b][1]):
if numbers[k] == 0:
tempRes = tempRes + queries[b][2]
tempRes = tempRes + numbers[k]
temp.append(tempRes)
tempRes = 0
return temp
JS解决方案：
有两种方法可以解决这个问题(Brute force Solution[Nested Loop](，这是一种在整个测试执行过程中以超时错误响应的方法，你需要用另一种时间复杂性来解决它，这是我的答案第一种方法O(N^2(，然后第二种方法优化为O(N(来解决超时错误。
JavaScript中的答案希望对您有所帮助
/*
-- Brainstorming --
Have 1-indexed Array [numbers] of length n;
Have numbers of queries (q). [2D Array]
Each Query => [startIdx i, endIdx r, number x]
Find => Sum of numbers between indexes i and r (both included)
if zero occured in range add x instead of it.
*/
// 1st Method: Brute force Solution [Nested Loop]
function findSum(numbers, queries) {
const sum = new Array(queries.length).fill(0);
for (let i = 0; i < queries.length; i++) {
// let j = queries[i][0] - 1 Cause numbers 1-index not 0
for (let j = queries[i][0] - 1; j < queries[i][1]; j++) {
if (numbers[j] === 0) {
sum[i] += queries[i][2];
} else {
sum[i] += numbers[j];
}
}
}
return sum;
}
// 2nd Method: The Optimized Solution Single Loop
function findSum(numbers, queries) {
const sums = [];
const subArraySum = [];
const zerosArr = [];
let zerosCount = 0;
for (let i = 0; i < numbers.length; i++) {
if (numbers[i] === 0) {
zerosCount++;
zerosArr[i] = zerosCount;
} else {
zerosArr[i] = zerosCount;
}
subArraySum[i] = numbers[i] + (subArraySum[i - 1] || 0);
}
for (let q of queries) {
const i = q[0] - 1;
const r = q[1] - 1;
const x = q[2];
let finalSum = subArraySum[r] - (subArraySum[i - 1] || 0) + (zerosArr[r] - (zerosArr[i - 1] || 0)) * x;
sums.push(finalSum);
}
return sums;
}
console.log("1st Test: " + findSum([5,10,10], [[1,2,5]])) // 15
console.log("2nd Test: " + findSum([-5,0], [ [2, 2 ,20] , [1,2,10]])) // 20 , 5
console.log("3rd Test: " + findSum([-1,-1,1,-4,3,-3,-4], [ [1, 4 ,2]])) // -5
console.log("4th Test: " + findSum([1000000000], [[1, 1,100]]))// 1000000000
console.log("5th Test: " + findSum([-1000000000], [[1, 1,100]]))// -1000000000您的代码每次查询需要一段线性时间。在线性时间中投资一次，以预计算部分和的数组。然后，每个查询都将在一个固定的时间内得到回答。
public static List<Long> findSum(List<Integer> numbers, List<List<Integer>> queries) {
// Write your code here
ArrayList<Long> arr = new ArrayList<>();
for(int i = 0; i < queries.size(); i++) {
int sum = 0;
for(int j = queries.get(i).get(0) - 1; j <= queries.get(i).get(1) - 1; j++) {
if(numbers.get(j) == 0){
sum += queries.get(i).get(2);
} else {
sum += numbers.get(j);
}
}
arr.add((long)sum);
sum = 0;
}
return arr;
}
逻辑尝试将每个索引与最后一个索引相加。但是使用0初始化第一个索引。计算零点也是如此。之后，只需用所需的索引减去左侧即可。索引中也有零值，但与查询相乘。给你，我无法公布答案。
C中的解决方案通过所有测试和时间限制
代码注释过多，因此最好在C编译器/编辑器上阅读
简单地说，您必须避免嵌套循环，尝试一次重复工作，使用如图所示的累积sume技术。
#include <stdio.h>
#include <stdlib.h>
long* findSum(int numbers_count, int* numbers, int queries_rows, int queries_columns, int** queries, int* result_count) {
//Dynamically create an array of longs to store the results and initialize it to 0 each element using calloc()
long * ResArray = (long*)calloc(queries_rows , (sizeof (long)));
//Dynamically create an array of longs to store accumelated zero counts, this array will exceed the size of numbers array by 1
//as the first element will be 0 and the last element will be the accumelated zero count of the numbers array
// numbers[] -> 1,0,2,0,0,3,5,0
// zeroFlagArr[] -> 0,1,1,2,2,3,3,4,4
long * zeroFlagArr = (long*)calloc(numbers_count+1 , (sizeof (long)));
//same as the zeroFlagArr but this array will store the accumelated sum of the numbers array
// numbers[] -> 1,0,2,0,0,3,5,0
// prefix_sum[] -> 0,1,1,3,3,3,6,11,11
long* prefix_sum = (long*) malloc((numbers_count + 1) * sizeof(long));
zeroFlagArr[0] =0;//first element of zeroFlagArr is 0, as nothing before index 0 in numbers[] to consider !
prefix_sum[0] = 0;//first element of prefix_sum is 0, as nothing before index 0 in numbers[] to sum up !
//loop through the numbers array and fill the zeroFlagArr and prefix_sum arrays
//this is done one time only every function call to be used in the queries loop
for (int i = 0; i < numbers_count; i++) {
//if currnet numbers[] element == 0, then the next element in the zeroFlagArr will be the previous element + 1
//note here we exceed i by one for both arrays as we accumelate what is behine in numbers[] array
if (numbers[i]== 0) {
zeroFlagArr[i+1] = zeroFlagArr[i] +1;
}
//else if it is any other number, then just use the last index value
else{
zeroFlagArr[i+1] = zeroFlagArr[i];
}
//fill the prefix_sum array with the accumelated sum of the numbers array
prefix_sum[i + 1] = prefix_sum[i] + numbers[i];
}
//loop the queries input
for (int i = 0 ; i <queries_rows ; i++) {
int startIndex = (queries[i][0] -1);// -1 because the input is indexing from 1 not 0
int endIndex = (queries[i][1] -1);// -1 because the input is indexing from 1 not 0
//index 0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,11,12
// numbers[] -> 1 ,2 ,3 ,4 ,5 ,0 ,5 ,0 ,6 ,8 ,0 ,0 ,9
// |<-------[1] to [9]------->|
// prefix_sum[] -> 0 ,1 ,3 ,6 ,10,15,15,20,20,26,34,34,34,43
// sum+= |<-------[10]-[1]------------>|
// zeroFlagArr[] -> 0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,2 ,2 ,2 ,3 ,4 ,4
// sum+= |<----{(2)-(0)} x load------->|
long sum = prefix_sum[endIndex + 1] - prefix_sum[startIndex];
sum += ((zeroFlagArr[endIndex+1] - zeroFlagArr[startIndex]) * queries[i][2] );
ResArray[i] = sum;
}
free(prefix_sum);
*result_count = queries_rows;
return ResArray;
}
int main()
{
int numbers_count = 2;
int numbers[] = {-5,0};
int queries_rows = 2;
int queries_columns = 3;
int **queries = (int**)malloc(queries_rows * sizeof(int*));
for (int i = 0; i < queries_rows; i++)
queries[i] = (int*)malloc(queries_columns * sizeof(int));
queries[0][0] = 2;
queries[0][1] = 2;
queries[0][2] = 20;
queries[1][0] = 1;
queries[1][1] = 2;
queries[1][2] = 10;
int result_count;
long* result = findSum(numbers_count, numbers, queries_rows, queries_columns, queries, &result_count);
for (int i = 0; i < result_count; i++) {
printf("%ld n", result[i]);
}
scanf( "%d" , &result_count);
return 0;
}
试试这个(在javascript中(：
function findSum(numbers, queries) {
// Write your code here
let sumArr = [];
for (let i = 0; i < queries.length; i++) {
let sum = 0;
let start = queries[i][0];
let end = queries[i][1] + 1;
let x = queries[i][2];
const newArr = numbers.slice(start, end);
newArr.forEach((item) => {
if (item === 0) {
sum = sum + x;
}
sum = sum + item;
});
sumArr.push(sum);
}
return sumArr;
}#!/usr/bin/python3
def solution(numbers, queries):
if not isinstance(numbers, list) and not isinstance(queries, list):
return
result = []
total = 0
for query in queries:
if len(query) == 3:
start = query[0]
end = query[1]
additional = query[2]
selection = numbers[start-1:end]
has_zeros = False
for el in selection:
if el == 0:
has_zeros = True
print(f"has_zeros: {has_zeros}")
print(f"selection: {selection}")
total = sum(selection)
if has_zeros:
total += additional
result.append(total)
return result
if "__main__" == __name__:
# 15
_input = [5, 10, 10]
_queries = [[1], [3], [1, 2, 5]]
print(f"input: {_input}")
print(f"queries: {_queries}")
_output = solution(_input, _queries)
print(f"ouput: {_output}")
Python中的解决方案3:
def findSum(numbers, queries):
a = [0]
b = [0]
for x in numbers:
a.append(a[-1] + x)
b.append(b[-1] + (x == 0)) if in subarray has 0, sum = sum + number x)
return [a[r] - a[l - 1] + x * (b[r] - b[l - 1]) for l, r, x in queries]