/** * https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/ * 1.同余定理:如果(a-b)/p=k k为整数,则a%p=b%p * 2.C++和Java中对[负数%正数]的结果以及修正: * 负%正=负 修正:(a%p+p)%p * */ public static void hanShu6(int[] nums, int target){ Map<Integer,Integer> hash=new HashMap<Integer,Integer>(); hash.put(0%target,1); int sum=0,ret=0; for (int x : nums) { sum += x; int r=(sum%target+target)%target; ret+=hash.getOrDefault(r,0); hash.put(r,hash.getOrDefault(r,0)+1); } }
/** * https://leetcode.cn/problems/subarray-sum-equals-k/ * 见图 * */ public static void hanShu5(int[] nums, int target){ Map<Integer,Integer> hash=new HashMap<Integer,Integer>(); hash.put(0,1); int sum=0,ret=0; for (int x : nums) { sum += x; ret+=hash.getOrDefault(sum-target,0); hash.put(sum,hash.getOrDefault(sum,0)+1); } }