370.範囲の追加

370 Range Addition

説明

長さの配列があると仮定します n すべてで初期化 0 とが与えられます に 更新操作。

各操作はトリプレットとして表されます。 [startIndex、endIndex、inc] サブアレイの各要素をインクリメントします A [startIndex ... endIndex] （startIndexおよびendIndexを含む） 株式会社 。

結局、変更された配列を返します に 操作が実行されました。

例：

与えられた：

長さ= 5、
更新= [
[1、3、2]、
[2、4、3]、
[0、2、-2]
]

出力：

[-2、0、3、5、3]

説明：

初期状態：
[0、0、0、0、0]

操作[1、3、2]を適用した後：
[0、2、2、2、0]

操作[2、4、3]を適用した後：
[0、2、5、5、3]

操作[0、2、-2]を適用した後：
[-2、0、3、5、3]

クレジット：
感謝します @ vinod23 この問題を追加し、すべてのテストケースを作成してくれました。

解決

ブルートフォース、O（mn）、S（1）、（TLE）

m：updates.length
n：長さ

class Solution { public int[] getModifiedArray(int length, int[][] updates) { if (length <1 || updates == null) { return new int[0] } int[] nums = new int[length] for (int[] update : updates) { for (int i = update[0] i <= update[1] ++i) { nums[i] += update[2] } } return nums } }

数学、O（m + n）、S（1）

素晴らしい質問です、実際、各更新[]について、対応する間隔のすべての値を実行する必要はありません。間隔の開始と終了、head + val、tail-valをマークするだけで済みます。このように、nums []をトラバースし、累積を記録し、nums [i]を合計するだけで済みます。

class Solution { public int[] getModifiedArray(int length, int[][] updates) { if (length <1 || updates == null) { return new int[0] } int[] nums = new int[length] for (int[] update : updates) { int start = update[0] int end = update[1] + 1 int val = update[2] nums[start] += val if (end < nums.length) { nums[end] -= val } } int sum = 0 for (int i = 0 i < nums.length ++i) { sum += nums[i] nums[i] = sum } return nums } }