JavaScript 陣列巢狀陣列中的部分和

---

在給定的問題陳述中，我們的任務是藉助 Javascript 功能獲取陣列巢狀陣列中的部分和。因此，我們將計算行的總和並給出結果。

理解問題

手頭的問題是計算陣列巢狀陣列的部分和。所以首先理解什麼是陣列巢狀陣列！陣列巢狀陣列表示每個專案本身代表一個數組。例如，參見下面的陣列巢狀陣列

[

[11, 12, 13],

[14, 15, 16],

[17, 18, 19]

]

位置 (i, j) 處的部分和是從輸入陣列的左上角到位置 (i, j) 處元素的所有元素的總和。

演算法

步驟 1：由於我們必須計算陣列巢狀陣列中的部分和，因此我們首先將建立一個函式來計算給定陣列的部分和，並將其命名為 sumOfSubarrays。並傳遞陣列作為引數 arr。

步驟 2：定義函式後，在函式內部首先檢查輸入陣列是否為空，如果為空則返回。

步驟 3：計算輸入陣列中的行數和列數。

步驟 4：建立一個二維陣列來儲存部分和的結果。

步驟 5：遍歷輸入陣列的每個元素，並根據位置和先前計算的部分和計算每個專案的區域性和。

步驟 6：位置 (i, j) 處的部分和使用以下公式計算。

步驟 7：該公式使用前一行和前一列的值。並減去左上角的值以避免重複計數。

示例

function sumOfSubarrays(arr) {
   if (arr.length === 0) return [];

   const numRows = arr.length;
   const numCols = arr[0].length;

   // Create a 2D array to store the partial sums
   const partialSums = new Array(numRows);
   for (let i = 0; i < numRows; i++) {
      partialSums[i] = new Array(numCols);
   }

   // Compute the partial sums
   for (let i = 0; i < numRows; i++) {
      for (let j = 0; j < numCols; j++) {
         if (i === 0 && j === 0) {
            partialSums[i][j] = arr[i][j];
         } else if (i === 0) {
            partialSums[i][j] = partialSums[i][j - 1] + arr[i][j];
         } else if (j === 0) {
            partialSums[i][j] = partialSums[i - 1][j] + arr[i][j];
         } else {
            partialSums[i][j] = partialSums[i - 1][j] + partialSums[i][j - 
1] - partialSums[i - 1][j - 1] + arr[i][j];
         }
      }
   }

   return partialSums;
}

// Example usage
const array = [
   [1, 2, 3],
   [4, 5, 6],
   [7, 8, 9]
];

const result = sumOfSubarrays(array);
console.log(result);

輸出

[ [ 1, 3, 6 ], [ 5, 12, 21 ], [ 12, 27, 45 ] ]

複雜度

在陣列巢狀陣列中查詢部分和的時間複雜度為 O(n)，對於上述函式以獲取給定陣列的部分和。並且該函式的空間複雜度也為 O(n)，因為我們正在儲存與相同長度的給定陣列的總和。

結論

正如我們在演算法中看到的，我們使用了動態方法來獲取給定陣列的部分和。並且該函式適用於任何大小的陣列。