【基础篇 - Day 24】 2020-11-24 - 37. 解数独

题目描述

Delete Sublist to Make Sum Divisible By K

入选理由

暂无

题目地址

https://binarysearch.com/problems/Delete-Sublist-to-Make-Sum-Divisible-By-K

前置知识

• 哈希表
• 同余定理及简单推导
• 前缀和

题目描述

You are given a list of positive integers nums and a positive integer k. Return the length of the shortest sublist (can be empty sublist ) you can delete such that the resulting list's sum is divisible by k. You cannot delete the entire list. If it's not possible, return -1.

Constraints

1 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 8, 6, 4, 5]
k = 7
Output
2
Explanation
We can remove the sublist [6, 4] to get [1, 8, 5] which sums to 14 and is divisible by 7.

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

class Solution {
    solve(nums, k) {
        let total = nums.reduce((prev, cur) => prev + cur, 0)
        const target = total % k
 
        let pres = 0, res = nums.length
        const map = { 0: -1 }
 
        for (let i = 0; i < nums.length; i++) {
            pres += nums[i]
            const mod = pres % k
            map[mod] = i
            const remain = map[(pres - target) % k]
            if (remain !== undefined) {
                res = Math.min(res, i - remain)
            }
        }
        return res === nums.length ? -1 : res
    }
}