924. 删除子列表以使总和可被 K 整除#

1
You are given a list of positive integers nums
2

3
and a positive integer k.
4

5
Return the length of the shortest sublist (can be empty sublist )
6

7
you can delete such that the resulting list's sum is divisible by k.
8

9
 You cannot delete the entire list.
10

11
If it's not possible, return -1.
12

13
Constraints
14

15
1 ≤ n ≤ 100,000 where n is the length of nums
16
Example 1
17
Input
18
nums = [1, 8, 6, 4, 5]
19
k = 7
20
Output
21
2
22
Explanation
23
We can remove the sublist [6, 4] to get [1, 8, 5]
24

25
which sums to 14 and is divisible by 7.

1
class Solution {
2
public:
3
    int solve(vector<int>& nums, int k) {
4
        int sum = 0;
5
        for(auto i : nums)
6
        {
7
            sum += i;
8
        }
9
        sum = sum % k;
10
        map<int, int> up;
11
        up[0] = -1;
12
        int pre = 0, n = nums.size();
13
        int ans = nums.size();
14
        for (int i = 0; i < n; i++)
15
        {
16
            pre += nums[i];
17
            int re = pre % k;
18
            up[re] = i;
19
            int x = pre - sum;
20
            int m = ((x % k) + k) % k;
21
            if (up.count(m)) ans = min(ans, i - up[m]);
22
        }
23
        return ans == nums.size() ? -1 : ans;
24
    }
25
};