前往
大廳
主題

LeetCode - 713. Subarray Product Less Than K 解題心得

Not In My Back Yard | 2022-08-08 12:00:04 | 巴幣 0 | 人氣 298

題目連結:


題目意譯:
給定一整數陣列 nums 以及一整數 k,回傳滿足所有元素乘積值嚴格小於 k 的連續子陣列之數量。

限制:
1 ≦ nums.length ≦ 3 × 10 ^ 4
1 ≦ nums[i] ≦ 1000
0 ≦ k ≦ 10 ^ 6



範例測資:
範例 1:
輸入: nums = [10,5,2,6], k = 100
輸出: 8
解釋: 乘積值小於 100 的 8 個子陣列為:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
注意到 [10, 5, 2] 並未被包含進來,因為乘積值 100 並沒有嚴格小於 k。

範例 2:
輸入: nums = [1,2,3], k = 0
輸出: 0


解題思維:
利用滑動視窗(Sliding Window,如這題)的精神來找出以每個索引值 i 作為結尾的最長連續子陣列之長度。

例如 nums = [2, 8, 7, 2, 3, 6, 6] 、 k = 64,可以看到:
以 nums[0] = 2 作為結尾的最長連續子陣列即為自己本身(因為 2 < 64);
以 nums[1] = 8 作為結尾的最長連續子陣列為 [2, 8](即從開頭開始,因為 2 × 8 < 64);
以 nums[2] = 7 作為結尾的最長連續子陣列為 [8, 7](因為 8 × 7 < 64);
以 nums[3] = 2 作為結尾的最長連續子陣列為 [7, 2](因為 7 × 2 < 64);
以 nums[4] = 3 作為結尾的最長連續子陣列為 [7, 2, 3](因為 7 × 2 × 3 < 64);
以 nums[5] = 6 作為結尾的最長連續子陣列為 [2, 3, 6](因為 2 × 3 × 6 < 64);
以 nums[6] = 6 作為結尾的最長連續子陣列為 [6, 6](因為 6 × 6 < 64)。

而對於一個索引值 i ,如果以其作為結尾的最長連續子陣列長度為 L 的話,則其將包含著額外 L - 1 個以 nums[i] 作為結尾的連續子陣列(剛好各自長度即為 1 ~ L - 1)。所以該索引值總計會貢獻 L 個子陣列。

因此在上例中我們可以看到答案是從
nums[0]:1
nums[1]:2
nums[2]:2
nums[3]:2
nums[4]:3
nums[5]:3
nums[6]:2
推得其為 1 + 2 + 2 + 2 + 3 + 3 + 2 = 15 個子陣列。而其他的 nums 也是同理。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作