ETH官方钱包

前往
大廳
主題

LeetCode - 1590. Make Sum Divisible by P 解題心得

Not In My Back Yard | 2023-09-20 12:00:14 | 巴幣 0 | 人氣 246

題目連結:


題目意譯:
給定一正整數陣列 nums,請移除最短的子陣列(可能為空)使得剩餘元素之總和可以被 p 整除。移除整個陣列是不被允許的。

回傳你需要移除的最短子陣列之長度。如果不可能達成要求,則回傳 -1。

一個子陣列定義為一陣列中一個連續區塊。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
1 ≦ p ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [3,1,4,2], p = 6
輸出: 1
解釋: nums 中的元素總和為 10,其並不被 6 整除。我們可以移除子陣列 [4],而剩餘元素總和為 6,其可被 6 整除。

範例 2:
輸入: nums = [6,3,5,2], p = 9
輸出: 2
解釋: 我們無法移除單一一個元素來得到可以被 9 整除的總和。最佳的方式為移除子陣列 [5,2],剩下的 [6,3] 可以得到總和值 9。

範例 3:
輸入: nums = [1,2,3], p = 3
輸出: 0
解釋: 現在總和為 6。其已經可以被 3 整除了。因此我們不需要移除任何東西。


解題思維:
基本上跟這題很類似。只是因為我們需要找到最短的子陣列,因此不是只找到一組移除後可以使總和變成 p 的倍數的子陣列即可,每一個潛在的子陣列我們需要找到並比較長度,取最小值即是所求。




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

創作回應

追蹤 創作集

作者相關創作

更多創作