search

leetcode-pp / 91alg-6-daily-check

91 算法第六期打卡仓库
28 stars 0 forks source link

【Day 24 】2022-01-04 - Delete Sublist to Make Sum Divisible By K #31

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

Delete Sublist to Make Sum Divisible By K

入选理由

暂无

题目地址

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

前置知识

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.

yetfan commented 2 years ago

思路 woshi zz......TUT 开始邮箱注册没成功，第一遍竟然写成两数加和的mod。。。。

字典维护 前缀余和 与 对应的所在的位置

代码

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

        mod = sum(nums) % k
        if mod == 0:
            return 0

        res = len(nums)
        mod_dict = {0:-1}
        sub_mod = 0

        for i, num in enumerate(nums):
            sub_mod = (sub_mod + num) % k
            target = (sub_mod - mod) % k

            if target in mod_dict:
                res = min(res, i-mod_dict[target])
                if res == 1 and res != len(nums):
                    return res
            mod_dict[sub_mod] = i
        if res == len(nums):
            return -1
        return res

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

yan0327 commented 2 years ago

这题可以在leetcode上：1590 https://leetcode-cn.com/problems/make-sum-divisible-by-p/ 找到类似题 思路： 不会，建议去看西法的题解。有详细的推导过程。这次先放个Go代码，再理解一下

func minSubarray(nums []int, p int) int {
    mode := 0
    sum := 0
    for i:=range nums{
        sum += nums[i]
    }
    if sum < p{
        return -1
    }
    mode = sum % p
    if mode == 0{
        return 0
    }
    hashmap := map[int]int{}
    hashmap[0] = -1
    tempSum := 0
    out := len(nums)
    for i:=0;i<len(nums);i++{
        tempSum += nums[i]
        tempMode := tempSum % p
        target := (tempMode - mode + p) % p
        if x,ok := hashmap[target];ok{
            out = min(out,i-x)
        }
        hashmap[tempMode] = i
    }
    if out == len(nums){
        return -1
    }else{
        return out
    }
}
func min(a,b int) int{
    if a < b{
        return a
    }
        return b
}

时间复杂度O（N） 空间复杂度O（N）

BpointA commented 2 years ago

思路

前缀和，第二次了还是记不太清...

Java代码

import java.util.*;

class Solution {
    public int solve(int[] nums, int p) {
        int m=0;
        int k=0;
        for (int n1:nums){k+=n1%p;}
        k=k%p;
        if(k==0){return 0;}

        HashMap<Integer,ArrayList> d=new HashMap<>();
        int n=nums.length;
        int pres[]=new int[n];
        pres[0]=nums[0];
        for(int i1=1;i1<n;i1++)
        {
            pres[i1]=pres[i1-1]+nums[i1];
        } 
        int ans=nums.length;
        for(int i=0;i<n;i++)
        {
            int x=(pres[i]-k)%p;
            if (d.get(x)!=null)
            {
                ArrayList<Integer> tmp=d.get(x);
                if(i-tmp.get(tmp.size()-1)<ans)
                {
                    ans=i-tmp.get(tmp.size()-1);
                }
            }
            ArrayList<Integer> tmp1=d.getOrDefault(pres[i]%p,new ArrayList<Integer>());
            tmp1.add(i);
            d.put(pres[i]%p,tmp1);
        }
        if(d.get(k)!=null)
        {  ArrayList<Integer> tmp2=d.get(k);
                if(tmp2.get(0)+1<ans)
                {
                    ans=tmp2.get(0)+1;
                }

        }

        if (ans==n)
        {return -1;}
        return ans;

    }
}

（这版在bi上能过，但是leetcode上过不了，还得学习怎么处理Java整数爆掉的解决方法）

把哈希表的值改成最近出现的位置，leetcode终于过了

class Solution {
    public int minSubarray(int[] nums, int p) {
        long k=0;
        for (int n1:nums){k+=n1%p;}
        k=k%p;
        if(k==0){return 0;}

        HashMap<Long,Integer> d=new HashMap<>();
        int n=nums.length;
        long pres[]=new long[n];
        pres[0]=nums[0];
        for(int i1=1;i1<n;i1++)
        {
            pres[i1]=pres[i1-1]+nums[i1];
        } 

        int ans=nums.length;
        int check=0;
        for(int i=0;i<n;i++)
        {
            long x=(pres[i]-k)%p;
            if (d.get(x)!=null)
            {
              ans=Math.min(i-d.get(x),ans);
            }
            if(pres[i]%p==k && check==0)
            {
                ans=Math.min(ans,i+1);
                check=1;
            }
            d.put(pres[i]%p,i);

        }

        if (ans==n)
        {return -1;}
        return ans;

    }
}
tian-pengfei commented 2 years ago 
class Solution {
public:
    //一开始时候还以为字串可以不是连续的呢,又是理解题意的失误
    int minSubarray(vector<int>& nums, int p) {
        int sum=0;
        for(auto const & val:nums){
            sum=(sum+val)%p;
        }
        int mod = sum%p;
        if(mod==0)return 0;
        int min_length=-1;
//        把对角线上的都填充上.
        vector<vector<int>> matrix(nums.size(),vector<int>(nums.size(),0));
        for (int i=0;i<nums.size();i++) {
            if((nums[i]-mod)%p==0)return 1;
            matrix[i][i] = nums[i];
        }
//平移对角线
        for (int length = 2; length < nums.size() ; ++length) {

            for(int i=0;i<nums.size()-length+1;i++){
                int j = i+length-1;
                // if(j>=nums.size())continue;
                int value = (matrix[i][j-1]+nums[j])%p;
                matrix[i][j] =value;
                if((value+p-mod)%p==0) return length;
            }
        }

        return min_length;

    }
};
laofuWF commented 2 years ago 
class Solution:
    def solve(self, nums, k):
        mod = 0
        total = 0
        for num in nums:
            total += num

        mod = total % k
        if mod == 0:
            return 0

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

        if res == len(nums):
            return -1
        return res
zhangzz2015 commented 2 years ago

关键点

代码

C++ Code:

int solve(vector<int>& nums, int k) {

    // sublist  f(i, j) = f(0, j) - f(0, i)    
    //  sum - f(i, j) = n*k 
    //  sum%k = f(i, j)%k
    //  sum%k = (f(0, j) - f(0, i))%k 
    //  sum%k = f(0, j)%k - f(0, i)%k 
    //  (sum%k + f(0, i)%k)%k = f(0, j)%k 
    // two sum problem. 

    long long sum =0; 
    vector<long long> prefix(nums.size()+1, 0); 
    for(int i=0; i< nums.size(); i++)
    {
       sum += nums[i]; 
       prefix[i+1] = sum; 
    }
    if(sum%k==0)
      return 0;
    int target_mod = sum%k;   
    unordered_map<int, int> record; 
    record[0] =0; 
    int ret = INT_MAX; 
    for(int i=1; i< prefix.size(); i++)
    {
        int jmodk = prefix[i]%k; 
        int itarget = (jmodk - target_mod+k)%k; 
        if(record.count(itarget))
        {
            ret = min(ret, ( i - record[itarget])) ;   
        }
        record[jmodk] = i; 
    }
    if(ret == nums.size())
       return -1; 
    return ret == INT_MAX? -1: ret;     
}
JudyZhou95 commented 2 years ago

思路

先看整个数组模k的余数是多少，得到的余数就是需要删除的sublist的模k余数(target)。利用前缀和的办法，遍历数组，记录从头开始的字数组的模k余数，两个余数差等于target的话，两sublist相减得到的sublist就满足要求。从满足要求的sublist中找到最短长度。

代码

def solve(nums, k):
    s = sum(nums)
    mod = s % k
    ans = len(nums)

    dic = {-1:0}  

    cur_total = 0
    for j in range(len(nums)):
        cur_total += nums[j]
        cur_mod = cur_total % k

        target = (cur_mod - mod + k) % k
        if target in dic:
            ans = min(ans, j-dic[target])
        dic[cur_mod] = j

    return ans

复杂度

TC: O(N)

SC: O(N)

rzhao010 commented 2 years ago

Thoughts

Code

public int solution(int[] nums, int k) {
  int tar = 0;
  for (int num: nums) {
    tar += num;
  }
  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;
}

Complexity Time: O(n) Space: O(min(n, k))

feifan-bai commented 2 years ago

思路

  1. Calculate the target = sum(nums) % k, equals to find the shortest array with sum % k = target.

  2. Using hashmap to record the prefix sum 代码

    class Solution:
def solve(self, nums, k):
    target = sum(nums) % k
    reminder = {0:-1}
    cur = 0
    n = len(nums)
    res = n

    for i, num in enumerate(nums):
        cur = (cur + num) % k
        reminder[cur] = i
        if (cur - target) % k in reminder:
            res = min(res, i - reminder[(cur - target) % k])
    return res if res < n else -1

    复杂度分析

    • 时间复杂度：O(N)
    • 空间复杂度：O(N)
zwmanman commented 2 years ago

class Solution(object): def minSubarray(self, nums, p): """ :type nums: List[int] :type p: int :rtype: int """

    helper = {0:-1}
    totalSum = 0

    for num in nums:
        totalSum += num

    r0 = totalSum % p

    if r0 == 0:
        return 0

    preSum = 0
    ans = float('inf')

    for idx, num in enumerate(nums):
        preSum += num

        r = preSum % p
        dr = (r - r0 + p) % p

        if dr in helper:
            l = helper[dr]
            ans = min(ans, idx - l)
        helper[r] = idx

    if ans < len(nums):
        return ans
    else:
        return -1
LinnSky commented 2 years ago

思路

数学问题

代码

   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;
    }
  }
LannyX commented 2 years ago

思路

同余定理 + 前缀和 + Hash Map

LeetCode 有[1000000000,1000000000,1000000000]测试用例，很麻烦

代码

class Solution {
    public int minSubarray(int[] nums, int p) {
        long sum = 0;
        //sum up
        for(int n : nums){
            sum += n;
        }
        //get the the sum Mod
        long sumMod = (sum + p) % p;
        if(sumMod == 0){
            return 0;
        }
        // hash map 
        Map<Long, Integer> map = new HashMap<>();
        long curMod = 0;
        int res = nums.length;
        //store the cur remainder and index
        map.put((long)0, -1);

        for(int i = 0; i < nums.length; i++){
            curMod = (curMod + nums[i] + p) % p;

            long target = (curMod - sumMod + p) % p;
            if(map.containsKey(target)){
                res = Math.min(res, i - map.get(target));
                if(res == 1 && res != nums.length){
                    return res;
                }
            }
            map.put(curMod, i);
        }
        return res == nums.length ? -1 : res;
    }
}

复杂度分析

ZacheryCao commented 2 years ago

Code

Hash Table

Code:

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

        return ans if ans != len(nums) else -1

Complexity

Time: O(N) Space: O(N)

zjsuper commented 2 years ago

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

Tesla-1i commented 2 years ago 
class Solution:
    def solve(self, nums, k):
        target = sum(nums) % k
        reminder = {0:-1}
        cur = 0
        n = len(nums)
        res = n

        for i, num in enumerate(nums):
            cur = (cur + num) % k
            reminder[cur] = i
            if (cur - target) % k in reminder:
                res = min(res, i - reminder[(cur - target) % k])
        return res if res < n else -1
ZhangNN2018 commented 2 years ago

复杂度

代码

class Solution:
    def solve(self, nums, k):
        #先计算出总体的数组和 total 模 k 的余数，记为 target，那么我们的目标就是找到一段模 k 等于 target 的子数组

        total = sum(nums) #求和
        mod = total % k #求余数

        res = len(nums) 
        total = 0
        dic = {0: -1} #用来最新的余数对应的下标
        for j in range(len(nums)): #遍历nums
            total += nums[j] #当前总和
            cur = total % k #当前的余数
            target = (cur - mod + k) % k 
            if target in dic:
                res = min(res, j - dic[target])
            dic[cur] = j

        if res == len(nums):
            return -1
        return res
zhiyuanpeng commented 2 years ago 
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

space min(N,k)time O(N)

xinhaoyi commented 2 years ago

思路一：前缀和+哈希表

sum表示原数组总和，sub表示要移除的子数组元素之和，根据同余定理，

(sum−sub)%p = 0 ⇒ sum % p = sub % p

即，我们应该寻找一个子区间，其对p取余的结果与sum对p取余结果相同，我们令mod=sum\%pmod=sum%p 那么同理，sub\%p=modsub%p=mod

在遍历前缀和数组时，我们依旧使用哈希表的方式记录下以往经过的前缀和对p求余的结果，以及其，当走到第j个元素时，如果想要在j之前找到满足条件的子数组，那么一定存在 pre[j] % p - pre[i] % p=mod

也就是pre[i] % p = pre[j] % p - mod

换句话说，我们要在哈希表中找有没有pre[j] % p - mod，如果有的话，就说明对应的j值存在，j - i就是我们要的子列长度，找其中最小值即可

代码

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length, mod = 0;
        for(int num : nums){
            mod = (mod + num) % p;
        }
        if(mod == 0){
            return 0;
        }
        int res = n, subMod = 0;
        Map<Integer, Integer> hashmap = new HashMap<>();
        hashmap.put(0, -1);
        for(int i = 0; i < n; i++){
            subMod = (subMod + nums[i]) % p;
            int target = (subMod - mod + p) % p;
            if(hashmap.containsKey(target)){
                res = Math.min(res, i - hashmap.get(target));
                if(res == 1 && res != n){
                    return res;
                }
            }
            hashmap.put(subMod, i);
        }
        if(res == n){
            return -1;
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

CodingProgrammer commented 2 years ago

思路

表示注册完，登录不了

代码

class Solution:
    def solve(self, nums, k):
        #先计算出总体的数组和 total 模 k 的余数，记为 target，那么我们的目标就是找到一段模 k 等于 target 的子数组

        total = sum(nums) #求和
        mod = total % k #求余数

        res = len(nums) 
        total = 0
        dic = {0: -1} #用来最新的余数对应的下标
        for j in range(len(nums)): #遍历nums
            total += nums[j] #当前总和
            cur = total % k #当前的余数
            target = (cur - mod + k) % k 
            if target in dic:
                res = min(res, j - dic[target])
            dic[cur] = j

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

复杂度

wenlong201807 commented 2 years ago

代码块


function deleteSubarray(arr, k) {
  // Stores the remainder of each
  // arr[i] when divided by K
  let mod_arr = new Array(arr.length);

  // Stores total sum of elements
  let total_sum = 0;

  // K has been added to each arr[i]
  // to handle negative integers
  for (let i = 0; i < arr.length; i++) {
    mod_arr[i] = (arr[i] + k) % k;

    // Update the total sum
    total_sum += arr[i];
  }

  // Remainder when total_sum
  // is divided by K
  let target_remainder = total_sum % k;

  // If given array is already
  // divisible by K
  if (target_remainder == 0) {
    return 0;
  }

  // Stores curr_remainder and the
  // most recent index at which
  // curr_remainder has occured
  let map = new Map();
  map.set(0, -1);

  let curr_remainder = 0;

  // Stores required answer
  let res = Number.MAX_SAFE_INTEGER;

  for (let i = 0; i < arr.length; i++) {
    // Add current element to
    // curr_sum and take mod
    curr_remainder = (curr_remainder + arr[i] + k) % k;

    // Update current remainder index
    map.set(curr_remainder, i);

    let mod = (curr_remainder - target_remainder + k) % k;

    // If mod already exists in map
    // the subarray exists
    if (map.has(mod)) res = Math.min(res, i - map.get(mod));
  }

  // If not possible
  if (res == Number.MAX_SAFE_INTEGER || res == arr.length) {
    res = -1;
  }

  return res;
}

时间复杂度和空间复杂度

hdyhdy commented 2 years ago

思路： 先找出原数组的和并做取模处理。然后利用前缀和以及同余公式来解决。

func minSubarray(nums []int, p int) int {
    mode := 0
    sum := 0
    for i:=range nums{
        sum += nums[i]
    }
    if sum < p{
        return -1
    }
    mode = sum % p
    //mode为余数
    if mode == 0{
        return 0
    }
    hashmap := map[int]int{}
    hashmap[0] = -1
    tempSum := 0
    out := len(nums)
    for i:=0;i<len(nums);i++{
        tempSum += nums[i]
        // tempSum为前缀和
        tempMode := tempSum % p
        // tempMode为前缀余数
        target := (tempMode - mode + p) % p
        // 根据同余定理，记prev[i]%m = currentMod//前的前缀，需要找到一个目标prev[j]（现在的前缀）的targetMod使得其前缀和的差为mod
        // targetMod = currentMod - mod (+ m)
        if x,ok := hashmap[target];ok{
            out = min(out,i-x)
        }
        //如果这个目标前缀和以前出现过。。。
        hashmap[tempMode] = i
        //对前缀余数进行定位
    }
    if out == len(nums){
        return -1
    }else{
        return out
    }
}
func min(a,b int) int{
    if a < b{
        return a
    }
        return b
}

时间复杂度：O(n)

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

yingliucreates commented 2 years ago 
function deleteSubarray(arr, k) {
  let mod_arr = new Array(arr.length);
  let total_sum = 0;
  for (let i = 0; i < arr.length; i++) {
    mod_arr[i] = (arr[i] + k) % k;
    total_sum += arr[i];
  }

  let target_remainder = total_sum % k;
  if (target_remainder == 0) {
    return 0;
  }
  let map = new Map();
  map.set(0, -1);

  let curr_remainder = 0;
  let res = Number.MAX_SAFE_INTEGER;

  for (let i = 0; i < arr.length; i++) {
    curr_remainder = (curr_remainder + arr[i] + k) % k;
    map.set(curr_remainder, i);
    let mod = (curr_remainder - target_remainder + k) % k;
    if (map.has(mod)) res = Math.min(res, i - map.get(mod));
  }

  if (res == Number.MAX_SAFE_INTEGER || res == arr.length) {
    res = -1;
  }

  return res;
}
shamworld commented 2 years ago 
class Solution:
    def solve(self, nums, k):
        if sum(nums) % k == 0:
            return 0
        mod = sum(nums)%k
        pre = {0:-1}
        total = 0
        ans = len(nums)
        for i in range(len(nums)):
            total += nums[i]
            cur = total%k
            target = (cur-mod + k)%k
            if target in pre:
                ans = min(ans, i - pre[target])
            pre[cur] = i

        return ans if ans != len(nums) else -1
anyingbinglong commented 2 years ago

思路： 先找出原数组的和并做取模处理。然后利用前缀和以及同余公式来解决。

func minSubarray(nums []int, p int) int { mode := 0 sum := 0 for i:=range nums{ sum += nums[i] } if sum < p{ return -1 } mode = sum % p //mode为余数 if mode == 0{ return 0 } hashmap := map[int]int{} hashmap[0] = -1 tempSum := 0 out := len(nums) for i:=0;i<len(nums);i++{ tempSum += nums[i] // tempSum为前缀和 tempMode := tempSum % p // tempMode为前缀余数 target := (tempMode - mode + p) % p // 根据同余定理，记prev[i]%m = currentMod//前的前缀，需要找到一个目标prev[j]（现在的前缀）的targetMod使得其前缀和的差为mod // targetMod = currentMod - mod (+ m) if x,ok := hashmap[target];ok{ out = min(out,i-x) } //如果这个目标前缀和以前出现过。。。 hashmap[tempMode] = i //对前缀余数进行定位 } if out == len(nums){ return -1 }else{ return out } } func min(a,b int) int{ if a < b{ return a } return b } 时间复杂度：O(n)

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

Moin-Jer commented 2 years ago

思路

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

代码

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

复杂度分析

TimmmYang commented 2 years ago

思路

哈希表+同余定理

代码

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

复杂度

时间：O(n), n为nums长度 空间：O(min(n, k))

biaohuazhou commented 2 years ago

思路

CV的一天

代码

   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;
    }

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

Flower-F commented 2 years ago

解题思路

先计算出 total % k 的值，根据同余定理，则问题转换为找到一段 % k 等于 target 的子数组 利用前缀和，子数组 [i:j] = pre[j] - pre[i-1]，然后利用哈希存储满足条件的子数组对应的下标 i 即可

代码

class Solution {
    solve(nums, k) {
        const map = new Map();
        map.set(0, -1); // 边界

        const target = nums.reduce((prev, cur) => (prev + cur)) % k;
        let res = nums.length, curSum = 0;
        for (let i = 0; i < nums.length; i++) {
            curSum = (nums[i] + curSum) % k; // 前缀和
            map.set(curSum, i); // 存储当前前缀和，因为要求最小，所以此处覆盖原来的存储结果无所谓
            const prevSum = this._floorMod(curSum - target, k);
            if (map.has(prevSum)) {
                res = Math.min(res, i - map.get(prevSum));
            }
        }

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

    // 解决正负数求余统一
    // 比如 -1 % 4 为 -1，而我们期望为 3，等同于先 +4 再模 4
    _floorMod(a, b) {
        return (a % b + b) % b;
    }
}

复杂度

时间：O(N) 空间：O(N)

yijing-wu commented 2 years ago

思路

代码


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

复杂度分析

charlestang commented 2 years ago

思路

设整个数组的总和是 S，需要删去的子数组的总和是 s，要想删去一个子数组后，剩余数字的总和被 P 整除，需要满足 S % P == s % p，也即 S 和 s 对P 同余。

我们可以计算数组的前缀和，然后，假设 i 是要删除的子数组的末尾，然后从 0 到 n -1 遍历 i。使用一个 哈希 以每个前缀和 对 P 的余数 做 key，下标做 value。 遍历过程中，每遍历到一个 i，我们需要找到使当前子串与 S 同余的前缀，只要去 哈希里搜索即可。

存储前缀和的空间是 O(n)，哈希的空间是 O(P)，时间复杂度是 O(n)。

代码

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        prefix = [0] * n

        for i in range(n):
            prefix[i] = nums[0] if i == 0 else prefix[i - 1] + nums[i]
        mod = prefix[n - 1] % p
        if mod == 0: return 0

        d = defaultdict(int)
        ans = n 
        for i in range(n):
            m = prefix[i] % p
            if m == mod:
                ans = min(ans, i + 1)
            key = (m + p - mod) % p
            j = d.get(key, -1)
            if j != -1:
                ans = min(ans, i - j)
            d[m] = i
        return ans if ans != n else -1
iambigchen commented 2 years ago

代码

JavaScript Code:


var floorMod = function (a, b) {
  return (a + 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
    }
}

复杂度分析

令 n 为数组长度。

chengyufeng6 commented 2 years ago

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

Husky-Gong commented 2 years ago 
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int count = 0, sum = 0;
        for(int a : A) {
            sum = (sum + a) % K;
            if(sum < 0) sum += K;  // Because -1 % 5 = -1, but we need the positive mod 4
            count += map.getOrDefault(sum, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}
spacker-343 commented 2 years ago

思路

牢记同余定理公式和 subArray = pre[j] - pre[i]，并进行简单推导，满足条件的长度就为 i - j

代码

class Solution {
    public int minSubarray(int[] nums, int p) {
        int sumMod = 0;
        for (int a : nums) {
            sumMod = (sumMod + a) % p;
        }
        Map<Integer, Integer> last = new HashMap<>();
        last.put(0, -1);
        int preMod = 0;
        int curMod = 0;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            curMod = (curMod + nums[i]) % p;
            last.put(curMod, i);
            preMod = (curMod - sumMod + p) % p;
            if (last.containsKey(preMod)) {
                ans = Math.min(ans, i - last.get(preMod));
            }
        }
        if (ans == nums.length) {
            return -1;
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

复杂度

时间复杂度：O(n) 空间复杂度: O(n)

haixiaolu commented 2 years ago

思路： 没有

需要好好了解一下前缀和和同余定理的推演

代码 / 抄的

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

复杂度分析

biscuit279 commented 2 years ago

思路：

同余定理:两个模k余数相同的数相减，得到的值仍能被k整除。 求数组中所有数之和模k的结果mod，问题转化成找一个模k等于mod的连续子数组 方法是计算前缀和，用字典保存前缀和模k的结果以及下标 ··· class Solution: def solve(self, nums, k): total = sum(nums) n = len(nums) mod = total % k

    ans = n
    dic = {0:-1}
    if mod == 0:
        return 0
    total = 0
    for j in range(n):
        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（min（n，k））

Brent-Liu commented 2 years ago

JavaScript Code:

var floorMod = function (a, b) { return (a + 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 } } 复杂度分析

令 n 为数组长度。

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

ggohem commented 2 years ago

思路：

前缀和和同余定理。

代码：

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;
    }
}

时空复杂度：

zol013 commented 2 years ago 
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        remainder = sum(nums) % p
        prefix = 0
        ans = float('inf')
        hashmap = {0:-1}

        for i in range(len(nums)):
            prefix += nums[i]
            hashmap[prefix % p] = i
            if (prefix - remainder) % p in hashmap:
                ans = min(ans, i - hashmap[(prefix - remainder) % p])

        return ans if ans < len(nums) else -1
Yachen-Guo commented 2 years ago

思路

前缀和+同余定理，重点在于(pre[j]-total)%k = pre[i-i]%k 公式的推导（假设被删除的是i~j段的数组）而presum[j]以及presum[i-i]可以通过前缀和得到。最短数组的确认是通过比较现有res和j-(i-1)的长度得到的。用到了hashmap储存presum%k的结果以及index

class Solution {

    public int solve(int[] nums, int k) {
        int total = 0;
        int prefix = 0;
        int res;
        for(int num : nums){
            total += num;
        }
        int target = Math.floorMod(total,k);

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

        for(int i = 0; i < nums.length; i++){
            prefix += nums[i];
            if(map.containsKey(Math.floorMod(prefix-target,k))){
                int res = Math.min(res,i - map.get(Math.floorMod(prefix-target,k)))
            }
            map.put(Math.floorMod(prefix,k),i);
        }

        return res;

    }
Toms-BigData commented 2 years ago

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

思路

前缀和加同余定理

golang代码

func solve(nums []int, k int) int {
    total := 0
    for i := 0; i < len(nums); i++ {
        total += nums[i]
    }
    mod := total % k
    ans := len(nums)
    total = 0
    hashmap := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        total+= nums[i]
        cur := total%k
        target := (cur-mod+k)%k
        if num,ok := hashmap[target];ok{
            ans = int(math.Min(float64(ans), float64(num)))
        }
        hashmap[cur] = i
    }
    if ans == len(nums){
        return -1
    }
    return ans
}

复杂度

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

cszys888 commented 2 years ago 
class Solution:
    def solve(self, nums, k):
        total = sum(nums)
        mod = total % k
        if mod == 0:
            return 0
        n = len(nums)
        pre_mod = {0:-1}
        cur = 0
        res = len(nums)
        for idx in range(n):
            cur += nums[idx]
            target = (cur - mod + k) % k
            if target in pre_mod:
                res = min(res, idx - pre_mod[target])
            pre_mod[cur] = idx
        if res == len(nums):
            return -1
        return res

time complexity: O(N) space complexity: O(min(N, k))

xuhzyy commented 2 years ago

思路

前缀和+同余定理

代码

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

复杂度分析

YuyingLiu2021 commented 2 years ago 
class Solution:
    def solve(self, nums, k):

        s = sum(nums)
        left = s % k
        if not left:
            return 0
        else:
            if s < k:
                return -1

        memo = {0:-1}
        v = 0
        res = float('inf')
        for i in range(len(nums)):
            v += nums[i]
            cur = v % k
            if cur >= left:
               if cur - left in memo:
                  res = min(res,i - memo[cur - left])
            else:
                if cur + k - left in memo:
                   res = min(res,i - memo[cur + k - left])
            memo[cur] = i
        return res if res != float('inf') and res != len(nums) else -1
tongxw commented 2 years ago

思路

关键思路是能想到，删去的那段连续子数组和sum[i:j]与数组总和sum[0:n-1]同余。

代码

class Solution {
    public int solve(int[] nums, int k) {
        int[] preSums = new int[nums.length];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        preSums[0] = nums[0];
        for (int i=1; i<nums.length; i++) {
            preSums[i] = preSums[i-1] + nums[i];
        }

        int sum = preSums[nums.length - 1];
        int mod = sum % k;

        map.put(0, -1);
        int ans = nums.length;
        for (int i=0; i<preSums.length; i++) {
            int preSumMod = preSums[i] % k;
            map.put(preSumMod, i);
            int target = (preSums[i] - mod) % k;
            if (map.containsKey(target)) {
                ans = Math.min(ans, i - map.get(target));
            }

        }

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

TC: O(n) SC: O(n)

ZZRebas commented 2 years ago

思路

在一个循环里面，遍历数组，依次求和，判断是否能被k整除。

代码(Python)

from functools import reduce
def fun(nums,k):
    n=0
    while n<len(nums):
        for i in range(len(nums)-n+1):
            new_nums=nums[:i]+nums[i+n:]
            sum=reduce(lambda x,y:x+y,new_nums)
            if sum%k == 0:
                return n
            if n==0:
                break
        n+=1
    if n==len(nums):
        return -1

nums = [1, 8, 6, 4, 5]
k = 7
res=fun(nums,k)
print(res)  #2

复杂度分析

xiao-xiao-meng-xiang-jia commented 2 years ago

class Solution {

public int solve(int[] nums, int k) {
    int total = 0;
    int prefix = 0;
    int res;
    for(int num : nums){
        total += num;
    }
    int target = Math.floorMod(total,k);

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

    for(int i = 0; i < nums.length; i++){
        prefix += nums[i];
        if(map.containsKey(Math.floorMod(prefix-target,k))){
            int res = Math.min(res,i - map.get(Math.floorMod(prefix-target,k)))
        }
        map.put(Math.floorMod(prefix,k),i);
    }

    return res;

}

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

Laurence-try commented 2 years ago 
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
qihang-dai commented 2 years ago

Intuition

use some math calculation: two number has the same mod by k then the reduction of them is mod by k.

While this we need to decide if the sum is mod by k after the delete of subarray, we store sum in prefixsum, and the deletie sum is prefix[j] - prefix[i].

Implementation

Use a HashMap and store the mod.

Math.floorMod to get positive and consistent mod for negative and positve number (very important, i fail to pass an OA because i didnt know this)

Time Complexity

O(n) only one round of iteration is needed

Space Complexity

O(n) use a hashmap to store mod and index

import java.util.*;

class Solution {
    public int solve(int[] nums, int k) {
        //(totalSUm - delete) % k == 0;
        // totalSUm % k = delet%k
        // let totalSum % k = totalMod
        // totalMod % k = totalMod;
        // delet%k = prefix[j] % k - prefix[i] %k = totalMod %k;
        // pre[i] % k = (pre[j] - totalMod) % k;
        int total = 0;
        for (int n : nums) {
            total += n;
        }
        int totalMod = Math.floorMod(total, k);

        Map<Integer, Integer> map = new HashMap();
        map.put(0, -1);
        int prefix = 0;
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            prefix += nums[i];
            int curMod = Math.floorMod(prefix, k);
            map.put(curMod, i);
            int afterMod = Math.floorMod(prefix - totalMod, k);
            // System.out.println(afterMod + "total" + totalMod +"pre" + prefix);
            if (map.containsKey(afterMod)) {
                int len = i - map.get(afterMod);
                System.out.println(i);
                res = len < res ? len : res;
            }
        }
        return res == nums.length ? -1 : res;
    }
}
jiaqiliu37 commented 2 years ago 
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:

        remainder = sum(nums) % p
        hashmap = {0:-1}
        ans = float('inf')

        for i in range(len(nums)):
            prefix = sum(nums[:i+1])
            hashmap[prefix % p] = i
            if (prefix - remainder) % p in hashmap:
                ans = min(ans, i - hashmap[(prefix - remainder) % p])

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

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