題目連結:
題目意譯:
給定一正整數陣列 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 的倍數的子陣列即可,每一個潛在的子陣列我們需要找到並比較長度,取最小值即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。