【Day 24 】2021-10-03 - Delete Sublist to Make Sum Divisible By K

[azl397985856]

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.

[cy-sues]

Code

class Solution {
    public int minSublist(int[] nums, int k) {
        int len = nums.length;
        int[] preSum = new int[len];
        int sum = 0;
        // 记录前缀和对k的余数
        for (int i = 0; i < len; i ++) {
            sum += nums[i] % k;
            sum %= k;
            preSum[i] = sum;
        }

        if (sum == 0) return 0;

        int res = len; // 最终结果不超过len,定义len为边界
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(sum, -1);
        for (int j = 0; j < len; j ++) {
            int remainder = preSum[j];
            int target = (remainder + sum) % k;
            map.put(target, j);

            if (map.containsKey(remainder)) {
                int size = j - map.get(remainder);
                res = Math.min(res, size);
                map.remove(remainder);
            }
        }

        if (res != len) return res;

        return -1;
    }
}

[iambigchen]

思路

老师题解的思路，前缀和+同余定理

代码

var minSubarray = function(nums, p) {
    var map = new Map();
    map.set(0,-1);
    var res = nums.length;
    var total = 0;
    var currSum = 0;
    for(let i =0; i<nums.length;i++){
        total+= nums[i];
    }
    total = getMod(total, p)
    for(let i = 0; i<nums.length;i++){
        currSum = getMod(nums[i]+currSum, p);
        map.set(currSum,i);
        var prevSum = getMod(currSum-total,p);
        if(map.has(prevSum)){
            res = Math.min(res,i-map.get(prevSum));
        }
    }
    return res === nums.length ? -1:res;
};

function getMod(a,b){
    let c = a % b
    return c < 0 ? c + b : c
}

复杂度

时间复杂度 O(n) 空间复杂度 O(min(n, k))

[cicihou]

class Solution:
    def solve(self, nums, p: int) -> int:
        tar = sum(nums) % p
        dic = {0: -1}
        prefix = 0
        res = len(nums)
        for i in range(len(nums)):
            prefix += nums[i]
            dic[prefix % p] = i
            modd = (prefix - tar) % p
            if modd in dic:
                res = min(res, i - dic[modd])
        return -1 if res == len(nums) else res

[PearlCoastal]

class Solution:
    def solve(self, nums, k):
        total = sum(nums)
        mod = total % k
        ans = len(nums)
        total = 0
        dic = {0: -1}
        for j in range(len(nums)):
            total += nums[j]
            cur = total % k
            target = (cur - mod + k) % k
            if target in dic:
                ans = min(ans, j - dic[target])
            dic[cur] = j
        if ans == len(nums):
            return -1
        return ans

[ai2095]

LC

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

Topics

• Hashtable
• List

Similar Questions

Easy

Medium

思路

gap = total % k sum[i:j] % k = gap --> (sum[0:j] - sum[0:i]) % k = gap use a hashtable to save the (gap- sum[0:j] %k +k) % k

代码 Python

class Solution:
    def solve(self, nums, k):

        gap = sum(nums) % k
        if gap == 0:
            return 0
        d = {}
        total = 0
        result = len(nums)
        for i in len(nums):
            total += nums[i]
            mod = total%k
            mod_diff = (mod - gap + k)%k
            if mod_diff in d:
                res = min(res, i - d[mod_diff])
            d[mod] = i
        return -1 if res == len(nums) else res

复杂度分析

时间复杂度： O(N)
空间复杂度：O(N)

[jsu-arch]

思路

前项和， 用hashmap记录结果

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        arr = nums
        mod_arr = [0] * n

    #Stores total sum of elements
        total_sum = 0
        for n in nums:
            total_sum +=n
    # calculate the target mode.
        target_mod = (total_sum+k) % k
        if target_mod ==0:
            return 0

    #Build up a hashset
        n, presum = len(nums), 0
    # Make sure we can access the first element
        hashmap = {0: -1}
        res = n
        for i in range(n):
            presum += nums[i]
            modulus = (presum + k) % k
            hashmap[modulus] = i
            if (modulus - target_mod + k) % k in hashmap:
                res = min(res, i - hashmap[(modulus - target_mod + k) % k])
        return res if res != n else -1

Complexity

Time Complexity : O(n) go over all element Space Complexity : O(n) storage

[RocJeMaintiendrai]

题目

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

思路

如果nums的和为100，k为6，那么目的就是找到（100 - X） % 6 == 0中的X，X可以为4， 10，16...即（4 + 6 n)，所以最终的目的就是找到最短的数组的和为(4 + 6 n)的即为结果。 找到子数组的和为sum = sum(nums) % k,再使用前缀和和hashmap来找到该结果，更新res为更小的值。

代码

class Solution {
    public int minSubarray(int[] nums, int k) {
        int n = nums.length, res = Integer.MAX_VALUE;
        long prefixSum[] = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        if (prefixSum[n] < k) return -1;
        long rmv = prefixSum[n] % k;
        if (rmv == 0) return 0;
        Map<Long, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n + 1; i++) {
            long rem = prefixSum[i] % k, target = (rem + k -rmv) % k;
            if (map.containsKey(target)) res = Math.min(res, i - map.get(target).get(map.get(target).size() - 1));
            map.computeIfAbsent(rem, a -> new ArrayList<>());
            map.get(rem).add(i);
        }
        return res == n || res == Integer.MAX_VALUE ? -1 : res;
    }
}

复杂度分析

时间复杂度

O（n）

空间复杂度

O（n）

[ZJP1483469269]

import java.util.*;

class Solution { public int solve(int[] nums, int k) { int tar = 0; for (int n : nums) tar += n; tar = Math.floorMod(tar, k); Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); int prefix = 0, res = nums.length; for (int i = 0; i < nums.length; i++) { prefix += nums[i]; int mod = Math.floorMod(prefix, k); map.put(mod, i); if (map.containsKey(Math.floorMod(prefix - tar, k))) res = Math.min(res, i - map.get(Math.floorMod(prefix - tar, k))); } return res == nums.length ? -1 : res; } }

[taojin1992]

Understand:

can remove empty list
remove a contiguous subarray, smallest
all positive elements
given array won't be empty

1 <= nums[i] <= 10^9, when we mod, avoid overflow

Plan:

if sum % p == 0: return 0

remaining sum = remaining
total sum = sum
the sum of deleted subarray = deleted_sum

to achieve remaining % p == 0, sum % p == deleted_sum % p

-> find the shortest subarray with its sum % p == sum % p

- Bruteforce:
enumerate all subarrays, get sum, track shortest. time O(n^2) * O(n), n = nums.length

- To optimize:
1. How to get sum more efficiently? 
- prefix sum
nums = [3,1,4,2]

actually we only care about remainder, cur sum % p

prefix_end_at_index_i - prefix_end_at_index_j = sum(nums[j+1, i]), length = i - j

j should start from -1, prefix_end_at_index_-1 = 0

map:
(prefixsum by index i) % p -> prefix index i

2. when we arrive at cur prefix, when "some" most recent prefix mod p == ?, s.t. subarray_sum % p == sum % p == all_remain

if cur prefix's remainder - "some" most recent prefix's remainder == sum % p, cool
but what if cur prefix's remainder - "some" most recent prefix's remainder < 0

1 2 3 4, p=3

index:
-1 0 1 2 3
prefix sum
0  1 3 6 10
mod:
0  1 0 0 1

subarray:[2,3], 5 % 3 = 2
prefix by index 2 - prefix by index 0 = 0 - 1 = -1
-1 % 3 = -1
(-4) % 3 = -1

after mod, + p to get positive mod

3. cur prefix's remainder - "some" most recent prefix's remainder == sum % p

(prefixMod[i] - prefixMod[j]) % p = sum's remainder % p, prefixMod[i] - prefixMod[j] < 0 might happen, % here means the positive mod, (-1) % 3 = 2

(prefixMod[i] - prefixMod[j] - sum's remainder) % p = 0, i > j

(prefixMod[i]  - sum's remainder) % p = prefixMod[j] % p

"some" most recent prefix's remainder = (prefixMod[i]  - sum's remainder) java mod operation (p) [+ p], if < 0, then + p to make it positive

Evaluate:

Time: O(nums.length)
Space: O(min(nums.length, p))

Code:

class Solution {
    public int minSubarray(int[] nums, int p) {
        // get remainder of the sum
        int remainder = 0;
        for (int num : nums) {
            // avoid overflow
            remainder = (remainder + num) % p;
        }

        if (remainder == 0) return 0; // no need to delete

        Map<Integer, Integer> preremainIndex = new HashMap<>();
        preremainIndex.put(0, -1);

        int minSubLen = nums.length;  // initialized as remove all
        int prefixMod = 0;

        for (int i = 0; i < nums.length; i++) {
            prefixMod = (prefixMod + nums[i]) % p;// avoid overflow
            preremainIndex.put(prefixMod, i);
            // when most recent prefix mod p == ?, subarray_sum % p == sum % p == all_remain

            int targetPrefixRemainder = (prefixMod - remainder + p) % p; // in case < 0

            if (preremainIndex.containsKey(targetPrefixRemainder)) {
                minSubLen = Math.min(minSubLen, i - preremainIndex.get(targetPrefixRemainder));
            }
        }

        // we can not remove all, if so, return -1
        return minSubLen == nums.length ? -1 : minSubLen;
    }
}

[kendj-staff]

import java.util.*;

class Solution {
    public int solve(int[] nums, int k) {
        int num = 0;
        for (int n : nums) {
            num += n;
        }
        int target = num % k;

        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int pre = 0;
        int res = nums.length;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            int mod = Math.floorMod(pre, k);
            map.put(mod, i);

            if (map.containsKey(Math.floorMod(pre - target, k))) {
                res = Math.min(res, i - map.get(Math.floorMod(pre - target, k)));
            }

        }
        return res == nums.length ? -1 : res;
    }
}

[Yufanzh]

Intuition

preSum + HashMap The simple mathematical idea is: residual = total % k we need to find a range [i, j] where sum[i,j] % k = residual sum[i:j] % k = residual means (sum[0:j] - sum[0:i]) % k = residual use a hashtable to save the (sum[0:i] + k - residual) % k

Algorithm in python3

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        #preSum + HashMap
        """step1. boundary condition. if sum of nums is divisible by p, return 0
                                      if sum < p, return -1
        """
        sumNum = sum(nums)
        rsd = sumNum % p
        if rsd == 0:
            return 0
        if sumNum < p:
            return -1

        """step2. create a hashmap to record the presum of the first ith sum
        so the idea is: if you find preSum[i] % p = preSum[j] %p = ans, then the first 0-i is the subarray that can be removed"""
        #We use a hashtable to store the last index of the prefix sum % p 
        preSum = {}
        preSum[0] = -1
        ans = sys.maxsize
        left = 0
        for i, num in enumerate(nums):
            left += num
            left %= p
            preSum[left] = i

            #check if its the aimed modulo
            aim = (p + left - rsd) % p # not sure why
            if aim in preSum:
                ans = min(ans, i - preSum[aim])
        #step3: another boundary condition: cannot remove the whole arraylist
        return ans if ans < len(nums) else -1

Complexity analysis

• Time complexity: O(N)
• Space complexity : O(N)

[Mahalasu]

思路

哈希表 + prefix，还有用到同余定理

class Solution:
    def solve(self, nums, k):
        total = sum(nums)
        mod = total % k

        ans = len(nums)
        total = 0
        dic = {0: -1}
        for j in range(len(nums)):
            total += nums[j]
            cur = total % k
            target = (cur - mod + k) % k
            if target in dic:
                ans = min(ans, j - dic[target])
            dic[cur] = j

        if ans == len(nums):
            return -1
        return ans

T: O(n) S: O(min(n,k))

[zhangzz2015]

思路

• 需要求 totalSum - sum[i , j] = n *k 。对于查找倍数的问题，利用余数定理 totalSum%k - sum[i,j]%k =0; sum [i j ] 利用前缀和转化 sum[i ,j] = sum[0, j] - sum[0, i-1] totalSum%k - (sum[i] - sum[j])%k =0 totalSum%k - sum[i]%k = sum[j]%k 转化为two sum 形式。每次记录前缀和的余数放入map。当前的余数计算 target - sum[i]%k 。为了避免的负数的问题。可利用小trick (target - sum[i]%k +k )%k 加上k 后再求余数的办法。时间负责度为O(N) ， 空间复杂度为O(N)。

int solve(vector& nums, int k) {

vector<int> prefixSum(nums.size()+1,0);
int sum =0; 
unordered_map<int, int> record; 
for(int i =0; i< nums.size(); i++)
   {
      sum +=nums[i]; 
      prefixSum[i+1] = sum; 
   } 

   if(sum%k==0)
     return 0; 
   int ret = INT_MAX;  
   int target = sum%k; 
   record[0] =0;   
   for(int i =1; i< prefixSum.size(); i++)
   {
       //  prefixSum[i]%k - prefixSum[j]%k = sum%k
       if(record.find( (prefixSum[i]%k -target +k)%k )!=record.end())
       {
           ret = min( ret, i - record[(prefixSum[i]%k -target +k)%k]);
           record[prefixSum[i]%k] = i;
       }
       else
       {
           record[prefixSum[i]%k] = i; 
       }
   }  
   if(ret ==INT_MAX || ret == nums.size())
    ret = -1; 
   return ret;   

}

[qyw-wqy]

// Search for a shortest subarray with sum % p = total sum % p.
// Use prefix sum to search for such a subarray. 
class Solution {
    public int minSubarray(int[] nums, int p) {
        int target = 0;
        for (int n : nums) target = (target + n) % p;
        if (target == 0) return 0;
        Map<Integer, Integer> map = new HashMap<>(); 
        map.put(0, -1);
        int res = Integer.MAX_VALUE;
        for (int i = 0, sum = 0; i < nums.length; i++) {
            sum += nums[i];
            sum %= p;
            if (map.containsKey((sum + p - target) % p)) {
                res = Math.min(res, i - map.get((sum + p - target) % p));
            }
            map.put(sum, i);
        }
        return res == nums.length ? -1 : res;
    }
}

Time O(n) Space: O(n)

[thinkfurther]

思路

用同余定理来避免反复搜索

代码

class Solution:
    def solve(self, nums, k):
        def floorMod(a,b):
            return a - a // b * b

        target = sum(nums)

        target = floorMod(target, k)
        map = {0:-1}

        prefix = 0
        res = len(nums)

        for i in range(len(nums)):
            prefix += num[i]
            mod = floorMod(prefix, k)
            map[mod] = i

            remaining = floorMod(prefix - target, k)

            if remaining in map:
                res = min(res, i - map[remaining] )

        return -1 if res == len(nums) else res

复杂度

时间复杂度 ：O(N)

空间复杂度：O(min(N,k))

[yanjyumoso]

class Solution:
    def solve(self, nums, k):
        tar_remainder = (sum(nums) + k) % k
        if tar_remainder == 0:
            return 0
        n, presum = len(nums), 0
        hashmap = {0: -1}
        res = n
        for i in range(n):
            presum += nums[i]
            modulus = (presum + k) % k
            hashmap[modulus] = i
            if (modulus - tar_remainder + k) % k in hashmap:
                res = min(res, i - hashmap[(modulus - tar_remainder + k) % k])
        return res if res != n else -1

[watchpoints]

思路

看好几次，没怎么看懂，参考大神思路

代码

class Solution {
public:
  int minSubarray(vector<int>& nums, int p) {
    const int n = nums.size();
    int r = accumulate(begin(nums), end(nums), 0LL) % p;
    if (r == 0) return 0;
    unordered_map<int, int> m{{0, -1}}; // {prefix_sum % p -> last_index}
    int s = 0;
    int ans = n;
    for (int i = 0; i < n; ++i) {
      s = (s + nums[i]) % p;
      auto it = m.find((s + p - r) % p);
      if (it != m.end())
        ans = min(ans, i - it->second);
      m[s] = i;
    }
    return ans == n ? -1 : ans;
  }
};

[Huangxuang]

思路

• 如果不能被整除，先找到整体余数，设为target, 那么就从nums[] 里面找到一个samllest subarray 让它的和是target， 一个subarray的和可以用prefix Sum，On就能解决

goal = (current_prefixSum_reminder - target + p) % p
用target来找hashmap里面是否已经存在需要的goal。

代码

class Solution {
    public int minSubarray(int[] nums, int p) {
        int target = 0, goal = 0, preSum = 0, res = Integer.MAX_VALUE;
        for (int i : nums) {
            target = (target + i) % p;
           // System.out.println("target = " + target);
        }

        if (target == 0) {
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap();
        map.put(0, 0);
        for (int i = 0; i < nums.length; i++) {
            preSum = (preSum + nums[i]) % p;
            goal = (preSum - target + p) % p;
           // System.out.println("preSum = " + preSum);
           // System.out.println("goal = " + goal);
            if (map.containsKey(goal)) {
                res = Math.min(res, i + 1 - map.get(goal));
             //   System.out.println("res = " + res);
            } 
            map.put(preSum, i + 1);  
        }

    return res < nums.length ? res : -1;

    }
}

复杂度分析

• O(n) 计算reminder target， O（n)计算refixsum
• O(n)的额外空间储存HashMap

[L-SUI]

class Solution: def solve(self, nums, k): n = len(nums) arr = nums mod_arr = [0] * n

#Stores total sum of elements
    total_sum = 0
    for n in nums:
        total_sum +=n
# calculate the target mode.
    target_mod = (total_sum+k) % k
    if target_mod ==0:
        return 0

#Build up a hashset
    n, presum = len(nums), 0
# Make sure we can access the first element
    hashmap = {0: -1}
    res = n
    for i in range(n):
        presum += nums[i]
        modulus = (presum + k) % k
        hashmap[modulus] = i
        if (modulus - target_mod + k) % k in hashmap:
            res = min(res, i - hashmap[(modulus - target_mod + k) % k])
    return res if res != n else -1

[user1689]

题目

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.

思路

同余定理+前缀和

python

class Solution:
    def deleteSublist(self, nums: List[int], k: int) -> int:
        # time n n为数组长度
        # space min((n, k)) 
        total = 0
        for i in range(0, len(nums)):
            total += nums[i]

        mod = total % k
        preSum = 0
        dic = {0:-1}
        ans = len(nums)
        for i in range(0, len(nums)):
            preSum += nums[i]
            curmod = (preSum) % k
            dic[curmod] = i
            # 这里比较麻烦的是需要处理正负的情况
            targetmod = (curmod - mod) if curmod >= mod else (curmod + k - mod)
            if targetmod in dic:
                ans = min(ans, i - dic[targetmod])
        return -1 if ans == len(nums) else ans

# 写法二
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        res = l = len(nums)
        C = sum(nums) % p
        if C == 0: 
            return 0
        cache = {C: -1}
        s = 0
        for i, num in enumerate(nums):
            s = (s + num) % p
            if s in cache:
                res = min(res, i - cache[s])
                if res == 1:
                    return res
            cache[(s + C) % p] = i
        if res == l:
            res = -1
        return res

复杂度分析

• time n
• space min(n, k)

相关题目

1. https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/
2. https://leetcode-cn.com/problems/continuous-subarray-sum/

[comst007]

Delete Sublist to Make Sum Divisible By K

---

思路

前缀和 + 哈希表

代码

• C++

int solve(vector<int>& nums, int k) {
    unordered_map<int, int> pos;
    int n = nums.size();
    vector<int> pre_sum(n + 1, 0);
    for(int ii = 1; ii <= n; ++ ii){
        pre_sum[ii] = pre_sum[ii - 1] + nums[ii - 1];
    }
    if(pre_sum[n] % k == 0){
        return 0;
    }
    int ans = n;
    int md = pre_sum[n] % k;
    pos[0] = 0;
    for(int ii = 1; ii <= n; ++ ii){
        int diff_res = (pre_sum[ii] - md) % k;
        if(pos.count(diff_res)){
            ans = min(ans, ii - pos[diff_res]);
        }
        pos[pre_sum[ii] % k] = ii;
    }
    if(ans == n) return -1;
    return ans;
}

---

复杂度分析

n为数组长度。

• 时间复杂度 O(n)。
• 空间复杂度 O(n)。

[leolisgit]

思路

这道题主要考察同余定理以及前缀和。 题目求s[i...j]使得，(s[0...n] - s[i...j]) % p == 0 --> s[0...n] % p == s[i...j] % p ---> 找到一个最短子数组，使得子数组的和和整个数组的和对p同余

1. 使用presum来求子数组的和
2. 使用hashmap记录presum以及index
3. 对于每一个s[0...j]，但是否存在一个i，使得(s[0...j] - s[0...i]) % p == s[i...j] % p == s[0...n] % p ---> s[0...i] % p == (s[0...j] - s[0...n]) % p

代码

class Solution {
    public int minSubarray(int[] nums, int p) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int sum = 0;
        for (int n : nums) {
            sum = (sum + n) % p;
        }
        if (sum == 0) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<>();
        // presum 1 indexed
        map.put(0, 0);
        int presum = 0;
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            presum = (presum + nums[i]) % p;
            // + p to avoid negative
            int key = (presum - sum + p) % p;
            if (map.containsKey(key)) {
                int l = map.get(key);
                res = Math.min(res, i + 1 - l);
            }
            map.put(presum, i + 1);
        }
        return res == nums.length ? -1 : res;
    }
}

复杂度

时间：O(n)
空间：O(n)

[Richard-LYF]

class Solution: def solve(self, nums, k): total = sum(nums) mod = total % k

    ans = len(nums)
    total = 0
    dic = {0: -1}
    for j in range(len(nums)):
        total += nums[j]
        cur = total % k
        target = (cur - mod + k) % k
        if target in dic:
            ans = min(ans, j - dic[target])
        dic[cur] = j

    if ans == len(nums):
        return -1
    return ans

[watermelonDrip]

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        total = sum(nums)
        target = total%k
        if target == 0:
            return 0
        if k == 1:
            return 0
        dict_pre = dict()
        dict_pre ={0:-1}

        pre = 0
        ans = len(nums)
        for j in range(n):
            pre += nums[j]
            tmp = (pre - target + k)%k
            print(tmp)
            if tmp in dict_pre:
                ans = min(ans, j- dict_pre[tmp])
                print(ans)
            dict_pre[pre%k] = j

        if ans == n:
            return -1
        return ans

[BpointA]

思路

同余定理+哈希表+前缀和。

Python3代码

class Solution:
    def solve(self, nums, k):
        from collections import defaultdict
        real_k=sum(nums)%k
        if real_k==0:
            return 0
        m=len(nums)
        pre=[0]*m
        pre[0]=nums[0]
        for i in range(1,m):
            pre[i]=pre[i-1]+nums[i]
        d1=defaultdict(list)
        d2=defaultdict(list)
        for i in range(m):
            d1[pre[i]%k].append(i)
            d2[(pre[i]-real_k)%k].append(i)
        res=m
        if real_k in d1:
            res=min(d1[real_k])+1
        for i in d1:
            if i not in d2:
                continue
            t1=d1[i]
            t2=d2[i]
            for a in t1:
                for b in t2:
                    if b>a:
                        res=min(res,b-a)
        if res==m:
            return -1
        return res

复杂度分析

时间复杂度：O(n)

时间复杂度：O(n)

[mokrs]

思路

• 前缀和+哈希表
• (sum - subSum) % p = 0 sum % p = subSum % p 记为 mod subSum = preSum[j] - preSum[i-1] preSum[i-1] % p = preSum[j] % p - subSum % p = preSum[j] % p - mod

int subarraysDivByK(vector<int>& nums, int p) {
    long long sum = 0;
    for (auto& num : nums)
        sum += num;
    if (sum < p) return -1;

    int mod = sum % p;
    if (mod == 0) {
        return 0;
    }

    unordered_map<int, int> mp = { { 0, -1 } };

    int res = nums.size();
    long long preSum = 0;

    for (int i = 0; i < nums.size(); ++i)
    {
        preSum += nums[i];
        int preMod = preSum % p;
        //避免preMod小于mod，出现负值
        int target = (preMod - mod + p) % p;

        if (mp.count(target))
            res = min(res, i - mp[target]);

        mp[preMod] = i;

    }
    return res == nums.size() ? -1 : res;
}

复杂度分析

• 时间：O(n)
• 空间：O(n)

[flame0409]

思路：

两个核心：

• 同余算法

• 前缀和

class Solution {

    public int solve(int[] nums, int k) {
        int target = 0;
        for(int i = 0; i < nums.length; i++){
            target += nums[i];
        }
        target  = Math.floorMod(target, k);
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int pre = 0, res = nums.length;
        for(int i = 0; i < nums.length; i++){
            pre = pre + nums[i];
            int mod = Math.floorMode(pre, k);
            map.put(mod, i);
            int keyToFind = Math.floorMod(pre - target, k);
            if(map.containsKey(keyToFind)){
                res = Math.min(res, i - keyToFind);
            }
        }
        if(res == nums.length){
            return -1;
        }
        return res;
    }
}

时间复杂度：O(n), n为长度

空间复杂度：O(min(n,k))，

[Laurence-try]

思路

同余定理和前缀和

代码

使用语言：Python3

class Solution:
    def solve(self, nums, k):
        total = sum(nums)
        mod = total % k
        if mod == 0:
            return 0
        ans = len(nums)
        total = 0
        dic = {0: -1}
        for j in range(len(nums)):
            total += nums[j]
            cur = total % k
            target = (cur - mod + k) % k
            if target in dic:
                ans = min(ans, j - dic[target])
            dic[cur] = j
        if ans == len(nums):
            return -1
        return ans

复杂度分析 时间复杂度：O(n) 空间复杂度：O(n)

[learning-go123]

思路

• 看的官方解题打卡

代码

• 语言支持：JavaScript

JavaScript Code:

let floorMod = function (a, b) {
    return ((a % b) + b) % b;
};

class Solution {
    solve(nums, k) {
        let map = new Map();
        map.set(0, -1)
        let target = nums.reduce((a, b) => a + b, 0) % k;

        let currSum = 0;
        let res = nums.length;
        for (let i = 0; i < nums.length; i++) {
            currSum = (nums[i] + currSum) % k;
            map.set(currSum, i);
            let prevSum = floorMod(currSum - target, k);
            if (map.has(prevSum)) {
                res = Math.min(res, i - map.get(prevSum));
            }
        }

        return res === nums.length ? -1 : res;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[m-z-w]

const solve = (nums, k) => {
  const total = nums.reduce((prev, current) => {
    return prev + current
  }, 0)
  const target = total % k
  const map = new Map()
  let prefix = 0
  let res = nums.length
  map.set(0, -1)
  for (let i = 0; i < nums.length; i++) {
    prefix += nums[i]
    let mod = prefix % k
    map.set(mod, i)
    if (map.has(floorMod(prefix - target, k))) {
      res = Math.min(res, i - map.get(floorMod(prefix - target, k)))
    }
  }
  return res
}

const floorMod = (num, k) => {
  return num > k ? num % k : floorMod(num + k, k)
}

时间：O(n) 空间：O(n)

[lizzy-123]

··· class Solution { public: int minSubarray(vector& nums, int p) { int mode = 0; int sum = 0;

    for (auto& n : nums)
        sum += n;

    if (sum < p) return -1;

    mode = sum % p;

    if (mode == 0) return 0;

    unordered_map<int, int> mp = {{0, -1}}; 
    int res = nums.size();

    int tmpSum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        tmpSum += nums[i];
        int tmpMode = tmpSum % p;
        int target = (tmpMode - mode + p) % p;
        if (mp.count(target))
            res = min(res, i - mp[target]);
        mp[tmpMode] = i;
    }

    return res == nums.size() ? -1 : res;
}

}; ···

[chaggle]

---

title: "Day 24 924. 删除子列表以使总和可被 K 整除" date: 2021-10-03T16:23:38+08:00 draft: true

924. 删除子列表以使总和可被 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.

题目思路

• 1、数学中的同余定理，以及前缀和的思路！

class Solution {
public:
    int solve(vector<int>& nums, int k) {
        int sum = 0;
        for(auto i : nums) 
        {
            sum += i;
        }
        sum = sum % k;
        map<int, int> up;
        up[0] = -1;
        int pre = 0, n = nums.size();
        int ans = nums.size();
        for (int i = 0; i < n; i++) 
        {
            pre += nums[i];
            int re = pre % k;
            up[re] = i;
            int x = pre - sum;
            int m = ((x % k) + k) % k;
            if (up.count(m)) ans = min(ans, i - up[m]);
        }
        return ans == nums.size() ? -1 : ans;
    }
}

复杂度

• 时间复杂度：O(n)

• 空间复杂度：O(n)

[RonghuanYou]

class Solution:
    def solve(self, nums, k):
        pre_sum = 0
        for num in nums:
            pre_sum += num

        # sum is divisible by p, return 0
        if pre_sum % k == 0: return 0

        mod = pre_sum % k

        dict = {0: -1}
        res = float("inf")

        pre_sum = 0
        for i in range(len(nums)):
            pre_sum = (nums[i] + pre_sum) % k
            target = (pre_sum - mod + k) % k
            if target in dict:
                res = min(res, i - dict[target])

            dict[pre_sum] = i

        return res if res < len(nums) else -1

[chen445]

代码

Brute Force

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        result=len(nums)
        prefix_nums =[nums[0]]
        for i in range(1,len(nums)):
            prefix_nums.append(prefix_nums[-1]+nums[i])
        if prefix_nums[-1]%p==0:
            return 0
        for i in range(len(nums)):
            for j in range(len(nums)):
                win_sum = 0
                if i <= j:
                    if i != 0:
                        win_sum = prefix_nums[j]-prefix_nums[i-1]
                    else:
                        win_sum = prefix_nums[j]
                    if (prefix_nums[-1]-win_sum)%p==0:
                        result=min(result,j-i+1)
        return -1 if len(nums)==result else result

Solution 2

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        hash_map={}
        target=sum(nums)%p
        if target == 0:
            return 0
        pre_fix_sum=0
        result=len(nums)
        for idx,num in enumerate(nums):
            mod=pre_fix_sum%p
            hash_map[mod]=idx
            pre_fix_sum+=num
            needed=(pre_fix_sum-target)%p
            if needed in hash_map:
                begin=hash_map[needed]
                result=min(result,idx-begin+1)
        return -1 if len(nums)==result else result

复杂度

Brute Force

Time: O(n^2)

Space: O(n)

Solution 1

Time: O(n)

Space: O(n)

[LareinaWei]

Thinking

Referring to the solution. First get the modular of total sum of the given array and the number p, store it in total_mod. The delete subarray sum should have the same modular with p, sum(subarray) % p = total_mod.

Code

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        dic = {}
        curr_sum = 0
        total_mod = sum(nums) % p
        if total_mod == 0: # if the total sum is dividable by p, then return 0
            return 0
        dic[0] = -1
        res = len(nums)
        for i in range(len(nums)):
            curr_sum += nums[i]
            k = curr_sum % p
            target = (k - total_mod + p) % p # +p to avoid negative numbers            
            if target in dic:
                res = min(res, i - dic[target])
            dic[k] = i

        if res == len(nums):
            return -1

        return res

Complexity

Time complexity: O(n) Space complexity: O(n)

[potatoMa]

思路

---

同余定理，以数组前缀和与k的余为key，创建一个检索器，因为0 <= key < k，故可以用长度为k - 1的数组代替哈希表

代码

---

class Solution {
    solve(nums, k) {
        const target = nums.reduce((a, b) => a + b, 0) % k;
        if (target === 0) return 0;
        let tempSum = 0, res = nums.length;
        const modList = new Array(k - 1);
        modList[0] = 0;
        for (let i = 0; i < nums.length; i++) {
            tempSum = (nums[i] + tempSum) % k;
            // 处理负数
            const key = (tempSum - target + k) % k;
            if (modList.hasOwnProperty(key)) {
                res = Math.min(res, i - modList[key] + 1);
            }
            modList[tempSum] = i + 1;
        }
        return res < nums.length ? res : -1;
    }
}

复杂度分析

---

时间复杂度：O(n)

空间复杂度：O(k)

[ysy0707]

思路：哈希表+前缀和+数学知识

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        //本体和560很像，只是判定条件不同
        HashMap<Integer,Integer> map = new HashMap<>();
        int presum = 0;
        int count = 0;
        map.put(0,1);
        for(int x : nums){
            presum += x;
            //当前 presum 与 K的关系，余数是几，当被除数为负数时取模结果为负数，需要纠正 所以加K
            int key = (presum % k + k) % k;
            //查询哈希表获取之前key也就是余数的次数
            if (map.containsKey(key)){
                count += map.get(key);
            }
            //存入哈希表当前key，也就是余数
            map.put(key,map.getOrDefault(key,0) + 1);
        }
        return count;
    }
}

时间复杂度：O(N) 空间复杂度：O(N)

[Zhang6260]

JAVA版本

思路：主要使用的是同余定理+前缀和。（将本题转换成找出最短的子串，该子串的和对k的模与全部数组和对k的模值相同）

class Solution {
   public int findSubstring(int[]nums,int k ){
       int  tar = 0;
       for(int n : nums) tar += n;
       tar = Math.floorMod(tar, k);
       Map<Integer, Integer> map = new HashMap<>();
       map.put(0,-1);
       int prefix = 0, res = nums.length;
       for(int i = 0; i< nums.length; i++){
            prefix += nums[i];
            int mod = Math.floorMod(prefix,k);
            map.put(mod,i);
           //与Math.floorMod(prefix-tar,k)余数相同的位置，
           //这说明该位置到当前位置i之间数的和对k的模也刚好为tar
            if(map.containsKey(Math.floorMod(prefix-tar,k)))
                res = Math.min(res,i-map.get(Math.floorMod(prefix-tar,k)));
       }
        return res == nums.length ? -1 : res;
   }
}

时间复杂度：O(n)

空间复杂度：O(n)

[QiZhongdd]

var floorMod = function (a, b) { return ((a % b) + b) % b; }; class Solution { solve(nums, k) { var map = new Map(); map.set(0, -1); var res = nums.length; var target = 0; var currSum = 0; for (let i = 0; i < nums.length; i++) { target += nums[i]; } target = target % k; for (let i = 0; i < nums.length; i++) { currSum = (nums[i] + currSum) % k; map.set(currSum, i); var prevSum = floorMod(currSum - target, k); if (map.has(prevSum)) { res = Math.min(res, i - map.get(prevSum)); } } return res === nums.length ? -1 : res; } }

[machuangmr]

思路

• 题意：移除一段最短连续子数组，使得剩下的数字和为 k 的整数倍
• 可以考虑使用前缀和 和 同余定理
• 前缀和：子数组 A[i:j] 的和就是 pres[j] - pres[i-1]，其中 pres 为 A 的前缀和

• 同余定理： 两个模 k 余数相同的数字相减，得到的值定可以被 k 整除。

  代码

  int total = 0;
      for (int num : nums) {
          total += num;
      }
      // 此时求得数组所有和 与 k 取余数
      total = Math.floorMod(total, k);
      Map<Integer, Integer> map = new HashMap<>();
      int prefix = 0, res = nums.length;
      for (int i = 0; i < nums.length; i++) {
          prefix += nums[i];
          // 前缀和，将每一个得到的和对k进行取余
          int temp = Math.floorMod(prefix, k);
          map.put(temp, i);
  
          // 如果当前前缀和的余 - （总数的值对 k 取余的值）， 然后再对k 进行取余的结果想等，
          // 那么剩下的值一定是k 的整数倍
          if (map.containsKey(Math.floorMod(prefix - total, k))) {
              res = Math.min(res, i - map.get(prefix - total));
          }
      }
      return res == nums.length ? -1 : res;

  复杂度

• 事件复杂度： O(N)
• 空间复杂度：O(N)

[JinMing-Gu]

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int mode = 0;
        int sum = 0;

        for (auto& n : nums)
            sum += n;

        if (sum < p) return -1;

        mode = sum % p;

        if (mode == 0) return 0;

        unordered_map<int, int> mp = {{0, -1}}; 
        int res = nums.size();

        int tmpSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            tmpSum += nums[i];
            int tmpMode = tmpSum % p;
            int target = (tmpMode - mode + p) % p;
            if (mp.count(target))
                res = min(res, i - mp[target]);
            mp[tmpMode] = i;
        }

        return res == nums.size() ? -1 : res;
    }
};

[hewenyi666]

题目名称

Delete Sublist to Make Sum Divisible By K

题目链接

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

题目思路

参考的题解: 同余定理和前缀和

code for Python3

class Solution:
    def solve(self, nums, k):
        total = sum(nums)
        mod = total % k
        if mod == 0:
            return 0
        ans = len(nums)
        total = 0
        dic = {0: -1}
        for j in range(len(nums)):
            total += nums[j]
            cur = total % k
            target = (cur - mod + k) % k
            if target in dic:
                ans = min(ans, j - dic[target])
            dic[cur] = j
        if ans == len(nums):
            return -1
        return ans

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[harleyszhang]

解题方法

哈希表 + 同余定理

int floorMod(const int& a, const int& b)
{
    return (a % b + b) % b;
}
int solve(vector<int>& nums, int k) {
    int allSum = 0;
    for (int& num : nums)
        allSum += num;

    allSum = floorMod(allSum, k);
    unordered_map<int, int> dict;
    dict[0] = -1;

    int preSum = 0;
    int minLen = nums.size();
    for (int i = 0; i < nums.size(); i++) {
        preSum += nums[i];
        int mod = floorMod(preSum, k);
        dict[mod] = i;

        if (dict.count(floorMod(preSum - allSum, k)))
            minLen = min(minLen, i - dict[floorMod(preSum - allSum, k)]);
    }
    return minLen == nums.size() ? -1 : minLen;
}

[ryzhao5]

前缀和

class Solution { public int solve(int[] nums, int k) { HashMap<Integer,Integer> map = new HashMap<>(); int pre = 0; int amount = 0; map.put(0,1); for(int i = 0; i < nums.length; i++){ pre += nums[i]; int key = (pre % k + k) % k; if (map.containsKey(key)){ amount += map.get(key); } map.put(key,map.getOrDefault(key, 0) + 1); } return amount; } }

[Mrhero-web]

前缀和

class Solution { public int solve(int[] nums, int k) { HashMap<Integer,Integer> map = new HashMap<>(); int pre = 0; int amount = 0; map.put(0,1); for(int i = 0; i < nums.length; i++){ pre += nums[i]; int key = (pre % k + k) % k; if (map.containsKey(key)){ amount += map.get(key); } map.put(key,map.getOrDefault(key, 0) + 1); } return amount; } }

[blanktime]

思路(mark 一下)

同余定理 + 前缀和

c++

int floorMod(const int& a, const int& b)
{
    return (a % b + b) % b;
}
int solve(vector<int>& nums, int k) {
    int allSum = 0;
    for (int& num : nums)
        allSum += num;

    allSum = floorMod(allSum, k);
    unordered_map<int, int> dict;
    dict[0] = -1;

    int preSum = 0;
    int minLen = nums.size();
    for (int i = 0; i < nums.size(); i++) {
        preSum += nums[i];
        int mod = floorMod(preSum, k);
        dict[mod] = i;

        if (dict.count(floorMod(preSum - allSum, k)))
            minLen = min(minLen, i - dict[floorMod(preSum - allSum, k)]);
    }
    return minLen == nums.size() ? -1 : minLen;
}

• 时间：O(n)
• 空间：O(min(n, k))

[Cartie-ZhouMo]

思路

同余定理+前缀和

代码

class Solution:
    def solve(self, nums, k):
        target = sum(nums)%k
        if target == 0: return 0
        ans = len(nums)
        s = 0
        hashdic = {0:-1}
        for i in range(len(nums)):
            s += nums[i]
            if (s-target)%k in hashdic:
                ans = min(ans, i-hashdic[(s-target)%k])
            hashdic[s%k] = i
        return -1 if ans == len(nums) else ans

复杂度

• 时间：O(N)
• 空间：O(min(N, k))

[liuyangqiQAQ]

class Solution1 {

    public static int solve(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int tar = Math.floorMod(sum, k);

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int pre = 0, res = nums.length;
        for (int i = 0; i < nums.length; i++) {

            pre += nums[i];
            int mod = Math.floorMod(pre, k);
            map.put(mod, i);

            if(map.containsKey(Math.floorMod(pre - tar, k))) {
                res = Math.min(res, i - map.get(Math.floorMod(pre - tar, k)));
            }

        }

        return res == nums.length? -1: res;
    }
}

[Toms-BigData]

【Day 24】Delete Sublist to Make Sum Divisible By K

思路

看的题解，自己理了一下思路 同余定理： 给定一个正整数m,如果两个整数a和b满足(a-b)能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)

前缀和： 数组中前n项的和

基本思想： 将数组求和与k取余，记为mod 遍历数组将前n项和与k取余（记为cur），存入字典，key为cur，value为n 当字典中存在两个key的和为mod 计算它们value的差值记为ans 返回最小的ans

Python3代码

class Solution:
    def solve(self, nums, k):
        sum_num = sum(nums)
        mod = sum_num%k

        ans = len(nums)
        total = 0
        num_dict = {0:-1}
        for i in range(len(nums)):
            total += nums[i]
            cur = total % k
            target = (cur - mod + k) % k
            if target in num_dict.keys():
                ans = ans if ans < i- num_dict[target] else i - num_dict[target]
            num_dict[cur] = i

        if ans == len(nums):
            return -1
        return ans

复杂度

时间:O(n) 空间:O(n)

[sxr000511]

var floorMod = function (a, b) { return ((a % b) + b) % b; }; class Solution { solve(nums, k) { var map = new Map(); map.set(0, -1); var res = nums.length; var target = 0; var currSum = 0; for (let i = 0; i < nums.length; i++) { target += nums[i]; } target = target % k; for (let i = 0; i < nums.length; i++) { currSum = (nums[i] + currSum) % k; map.set(currSum, i); var prevSum = floorMod(currSum - target, k); if (map.has(prevSum)) { res = Math.min(res, i - map.get(prevSum)); } } return res === nums.length ? -1 : res; } }