[leetcode 前綴和]

525. 連續數組 M

:::details

給定一個二進制數組 nums , 找到含有相同數量的 0 和 1 的最長連續子數組，并返回該子數組的長度。

示例 1:

輸入: nums = [0,1]
輸出: 2
說明: [0, 1] 是具有相同數量 0 和 1 的最長連續子數組。

示例 2:

輸入: nums = [0,1,0]
輸出: 2
說明: [0, 1] (或 [1, 0]) 是具有相同數量0和1的最長連續子數組。

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1

解題思路

因為只會出現0或1，求相同數量的最長連續子數組，所以為了方便，我們把0定義為-1，當前綴和等于0時，說明，當前子數組的01相等。

func findMaxLength(nums []int) (maxLength int) {n := len(nums)/**記錄前綴和出現的下標*/hash := map[int]int{0: -1}k := 0for i := 0; i < n; i++ {if nums[i] == 0 {k--} else {k++}if prevIndex, ok := hash[k]; ok {maxLength = max(maxLength, i-prevIndex)} else {hash[k] = i}}return maxLength
}func max(a, b int) int {if a > b {return a}return b
}

:::

523. 連續的子數組和 - 力扣（LeetCode）M

:::details

給你一個整數數組 nums 和一個整數 k ，編寫一個函數來判斷該數組是否含有同時滿足下述條件的連續子數組：

子數組大小至少為 2 ，且
子數組元素總和為 k 的倍數。
如果存在，返回 true ；否則，返回 false 。

如果存在一個整數 n ，令整數 x 符合 x = n * k ，則稱 x 是 k 的一個倍數。0 始終視為 k 的一個倍數。

示例 1：

輸入：nums = [23,2,4,6,7], k = 6
輸出：true
解釋：[2,4] 是一個大小為 2 的子數組，并且和為 6 。
示例 2：

輸入：nums = [23,2,6,4,7], k = 6
輸出：true
解釋：[23, 2, 6, 4, 7] 是大小為 5 的子數組，并且和為 42 。
42 是 6 的倍數，因為 42 = 7 * 6 且 7 是一個整數。
示例 3：

輸入：nums = [23,2,6,4,7], k = 13
輸出：false

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/continuous-subarray-sum
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路

因為題目要求的是子數組元素總和是k的倍數，也就是說，需要取模運算。

所以，在求前綴和的時候，直接求余數，當出現相同余數的時候，說明當前子數組的前綴和符合倍數要求，然后判斷子數組長度，如果符合條件則直接返回。

func checkSubarraySum(nums []int, k int) bool {n := len(nums)if n < 2 {return false}/**規定空的前綴的結束下標為 -1，由于空的前綴的元素和為 0，因此在哈希表中存入鍵值對 (0,-1)。*/prevSum := map[int]int{0: -1}remainder := 0for i, num := range nums {remainder = (remainder + num) % kif prevIndex, ok := prevSum[remainder]; ok {if i-prevIndex >= 2 {return true}} else {prevSum[remainder] = i}}return false}