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]);
}

时间和空间复杂度

上述代码的时间复杂度为O(Q)，其中Q是查询数。

上述代码的空间复杂度为O(N)，因为我们创建了一个新数组来存储数组元素的前缀和。

结论

在本教程中，我们实现了一个JavaScript程序，用于对数组逆时针旋转k位后的区间和查询。数组的逆时针旋转是指将给定数组的所有元素向左旋转给定索引数。我们实现了两种方法，第一种是时间复杂度为O(Q*N)的朴素方法，另一种是时间复杂度为O(Q)的前缀和方法。