JavaScript 数组按K索引逆时针旋转的范围求和查询

逆时针旋转数组意味着将给定数组的所有元素向左旋转给定的索引数。在本文中，我们将实现一个JavaScript程序，用于按k索引逆时针旋转数组的范围求和查询。

问题介绍

在这个问题中，我们有一个包含一些整数的数组和另一个数组，其中包含成对形式的值。每对将是当前查询所需的旋转次数，经过给定次数的旋转后，我们将获得一个范围，并需要回答该给定范围中元素的总和。示例，

示例1：

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [3, 1, 4]
Output 14

解释

旋转次数为3，所以经过3次旋转后的数组是4 5 6 1 2 3。

在范围1到4内的元素是5、6、1和2。所以，它们的和是14。

示例2

Input
Given array: [1, 2, 3, 4, 5, 6] 
Query: [8, 0, 3]
Output 18

说明

旋转次数为8，所以经过8次旋转后的数组等于8%(数组的长度)次旋转，因为在数组长度的次数旋转后，同样的数组又出现，意味着8次旋转等同于2次旋转。

因此，经过8次旋转后的数组为3 4 5 6 1 2。

在范围内，0到3的元素是3、4、5和6。所以，它们的和为18。

简单方法

在简单方法中，我们将简单地按照查询数组中指定的步骤执行所有步骤。示例，如果给定要旋转数组，则我们将按照给定的次数旋转数组元素，然后检查范围内元素的和。让我们看一下它的代码−

示例

// function to answer the queries 
function getSum(arr, rotations, L, R){
   var len = arr.length 
   var rot = rotations % len;
   var temp = new Array(len);

   // rotating the given array
   for(var i =0;  i< len - rot; i++ ){
      temp[i] = arr[i + rot];
   }

   // getting the last elements 
   for(var i = 0; i < rot; i++)    {
      temp[len-rot+i] = arr[i];
   }

   // getting the required sum
   var sum = 0;
   for(var i = L; i<=R; i++){
      sum += temp[i];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]

// defining the queries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]]

// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(arr, queries[i][0], queries[i][1], queries[i][2]);
}

时间和空间复杂度

上述代码的时间复杂度为O(Q*N)，其中Q是查询的数量，N是数组的大小。

上述代码的时间复杂度为O(N)，因为我们创建了一个大小为N的新数组。

前缀和方法

在前缀和方法中，我们将创建一个前缀和数组，前缀和数组的每个索引包含当前索引之前所有元素的和。让我们看看代码示例―

示例

// function to answer the queries 
function getSum(preSum, rotations, L, R){
   var len = preSum.length 
   var rot = rotations % len;

   // updating L and R 
   L = (L + rot) %len
   R = (R + rot) %len
   var sum = 0;
   if(L <= R) {
      if(L == 0) {
         sum = preSum[R];
      }
      else{
         sum = preSum[R]-preSum[L-1];
      }
   }
   else{
      sum += preSum[R];
      sum += preSum[len-1]-preSum[L-1];
   }
   console.log("The sum of the elements in the range " + L + " to " + R + " after " + rotations + " number of rotations is " + sum);
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]
var preSum = new Array(arr.length)
preSum[0] = arr[0]
for(var i = 1; i<arr.length; i++){
   preSum[i] = preSum[i-1] + arr[i]
}

// defining the quries array 
var queries = [ [ 3, 1, 4], [ 8, 0, 3]] 

// traversing over the given array 
for(var i = 0; i<queries.length; i++){
   getSum(preSum, queries[i][0], queries[i][1], queries[i][2]);
}