Make Sum Divisible by P
给一个数组nums和一个p, 求删去最小的子数组后的数字和可以整除p.
let s = sum of nums, r = s mod p -> r = (s + p) mod p
因为我们知道presum可以用两个指针表示其中间隔的和. let (i, j) = indexs in presum where 0 <=i <= j <= presum.length.
since r = (s + p) mod p, then r = (pre[j] – pre[i] + p) mod p
因为我们知道2sum中, 两个index可以用O(n)的space换取O(n^2) -> O(n)的时间.
since r = (pre[j] – pre[i] + p) mod p, then pre[i] =(pre[j] – r + p) % p;
所以我们用map存pre[i]即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { public int minSubarray(int[] nums, int p) { long sum = 0; for(int n : nums){ sum += n ; } if(sum % p == 0) return 0; if(sum < p) return -1; int t = (int) (sum % p); int res = nums.length; Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); int[] pre = new int[nums.length + 1]; for(int i = 1; i < nums.length + 1; i++) { pre[i] = (pre[i-1]%p + nums[i - 1]%p)%p; } for(int i = 0; i <= nums.length; i++) { int y = (int) (pre[i] % p); if(map.containsKey((y - t + p)%p)) res = Math.min(res, i - map.get((y - t + p)%p)); map.put(y, i); } if(res == nums.length) return -1; return res; } } |