Hackerrank 子数组求和问题 - 超时测试用例

Question

这是来自 hackerrank 的一个问题，我有一个解决方案，但有一些测试用例由于超出时间限制而失败。我不知道更好的解决方案。

求子数组中元素的总和（如果子数组中有 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;
}

Answer 1

正如@Annity建议的，您需要维护两个数组：

\n

\n
1. 到目前为止所有数字的总和。在索引的任何一点，它都应该具有所有先前数字的总和。
\n
2. 与上面相同，但它应该具有所有先前零的总数。
\n

\n

您应该避免嵌套循环以降低时间复杂度。这是一个 JavaScript 解决方案：

\n

\r\n

\r\n

function\xc2\xa0 findSum(numbers, \xc2\xa0queries)\xc2\xa0 {\n\n  let\xc2\xa0 result\xc2\xa0 = \xc2\xa0 [];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  let\xc2\xa0 subArraySum\xc2\xa0 = \xc2\xa0 [];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  let\xc2\xa0 countZero\xc2\xa0 = \xc2\xa0numbers[0]\xc2\xa0 == \xc2\xa00\xc2\xa0 ? \xc2\xa01\xc2\xa0 : \xc2\xa00;\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  let\xc2\xa0 zeroArr\xc2\xa0 = \xc2\xa0 [];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  zeroArr[0] = \xc2\xa0countZero;\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  subArraySum[0]\xc2\xa0 = \xc2\xa0numbers[0];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  for (let\xc2\xa0 i = 1;\xc2\xa0 i <= \xc2\xa0numbers.length - 1;\xc2\xa0 i++)\xc2\xa0 {\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n    if (numbers[i]\xc2\xa0 == \xc2\xa00) {\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      countZero++;\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      zeroArr[i]\xc2\xa0 = \xc2\xa0countZero;\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n    }\xc2\xa0\n    else\xc2\xa0 {\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      zeroArr[i]\xc2\xa0 = \xc2\xa0countZero;\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n    }\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n    subArraySum[i]\xc2\xa0 = subArraySum[i - 1]\xc2\xa0 + \xc2\xa0numbers[i];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  }\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n\n  for (let\xc2\xa0 q\xc2\xa0 of \xc2\xa0queries)\xc2\xa0 {\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n    if (q.length\xc2\xa0 == \xc2\xa03)\xc2\xa0 {\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      let\xc2\xa0 i\xc2\xa0 = \xc2\xa0q[0];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      let\xc2\xa0 j\xc2\xa0 = \xc2\xa0q[1];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      let\xc2\xa0 x\xc2\xa0 = \xc2\xa0q[2];\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      let\xc2\xa0 sum\xc2\xa0 = \xc2\xa00;\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      sum\xc2\xa0 = \xc2\xa0subArraySum[j - 1] - ((i - 2\xc2\xa0 < \xc2\xa00\xc2\xa0)\xc2\xa0 ? \xc2\xa00\xc2\xa0 : \xc2\xa0subArraySum[i - 2]);\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      sum\xc2\xa0 = \xc2\xa0sum\xc2\xa0 + \xc2\xa0(zeroArr[j - 1] - ((i - 2\xc2\xa0 < \xc2\xa00\xc2\xa0)\xc2\xa0 ? \xc2\xa00\xc2\xa0 : \xc2\xa0zeroArr[i - 2])) * x;\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n      result.push(sum);\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n    }\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  }\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\n  return\xc2\xa0 result;\n}\nconsole.log(findSum([5, 10, 15], [\n  [1, 2, 5]\n]))\nconsole.log(findSum([0, 10, 15], [\n  [1, 2, 5]\n]))

\r\n

\r\n

\r\n

\n