今天搞一個(gè)簡(jiǎn)單的算法
先上題目：
沒(méi)有用前綴 && hash 思想前徒河，我們干擼的代碼是這樣子的娇妓。
public int subarraySum(int[] nums, int k) {
// 構(gòu)造前綴和
int res =0;
int tempSum = 0;
int[] preSum = new int[nums.length+1];
// 累加和放入數(shù)組
for (int i = 1; i < nums.length+1; i++) {
tempSum += nums[i-1];
preSum[i] = tempSum;
}
// O^2 遍歷伐庭，獲取的區(qū)間和是K的值
for(int j=nums.length;j>=0;j--) {
for(int i=0;i<j;i++) {
if(preSum[j] - preSum[i] == k) {
res +=1;
}
}
}
return res;
}
AC用爪，但是結(jié)果用時(shí)很長(zhǎng)原押，不開(kāi)心??
那前綴&hash到底是什么，下面是題解代碼：
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0;
int ret = 0;
for(int i = 0; i < nums.length; ++i) {
sum += nums[i];
if(map.containsKey(sum-k)) // sum - k <==> j+1 j+2 ... i 子數(shù)組和為k 0到j(luò)子數(shù)組和為sum - k
ret += map.get(sum-k);
map.put(sum, map.getOrDefault(sum, 0)+1);
}
return ret;
}
代碼里的Map記錄的是同樣的和出現(xiàn)的次數(shù)偎血，對(duì)每一個(gè)累計(jì)和sum诸衔，判斷map里是否有sum-k
為什么是sum-k呢，why 颇玷？笨农？？
仔細(xì)想想
A[i] = A[0] + A[1] + A[2]+ …… +A[i]
A[j] = A[0] + A[1] + A[2]+ …… +A[j]
如果A[j] - A[i] = A[i+1] + A[i+2] + …… +A[j] = k 的話帖渠，從i+1到j(luò)是滿足條件的一個(gè)解把A[i]的值放入map中谒亦，當(dāng)A[j]的值是A[i]+k的話，是滿足條件的解阿弃，也就是判斷一下sum -k 是否已經(jīng)存在map里诊霹，統(tǒng)計(jì)符合這樣A[j]，答案找到了渣淳。時(shí)間復(fù)雜度O(n)脾还，AC結(jié)果也快了好多。
趁熱打鐵入愧，再看一道題：
思路一致鄙漏，需要注意的知識(shí)點(diǎn)：
java中負(fù)數(shù)做取模（%）運(yùn)算嗤谚，結(jié)果是負(fù)數(shù)，對(duì)應(yīng)的整數(shù)結(jié)果應(yīng)該是k+（sum%k）
public int subarraysDivByK(int[] A, int K) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int preSum = 0;
for (int i = 0; i < A.length; i++) {
preSum += A[i];
int temp = preSum % K < 0 ? (K + preSum % K) : preSum % K;
if (map.containsKey(temp)) {
res += map.get(temp);
}
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
return res;
}
