題目
給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù)?k ，請(qǐng)找到該數(shù)組中和為?k?的連續(xù)子數(shù)組的個(gè)數(shù)。
示例 1：
輸入:nums = [1,1,1], k = 2
輸出: 2
解釋: 此題 [1,1] 與 [1,1] 為兩種不同的情況
示例 2：
輸入:nums = [1,2,3], k = 3
輸出: 2
提示:
- 1 <= nums.length <= 2 * 104
- 1000 <= nums[i] <= 1000
- 107?<= k <= 107
解題思路
前置知識(shí)
前綴和
前綴和：顧名思義，是要求前綴的總和，什么是前綴，對(duì)于一個(gè)存放數(shù)字的數(shù)組而言，前綴就是指的數(shù)組的前k項(xiàng)，因此對(duì)應(yīng)的前綴和就是數(shù)組前k項(xiàng)的和。前綴和一般用來(lái)求數(shù)組中連續(xù)段子數(shù)組的值的和，類似于等差數(shù)列中利用等差數(shù)列的和來(lái)求某一段子數(shù)列的和：
?舉個(gè)例子：
我們有一個(gè)數(shù)組nums = [2,4,6,1,4]
下面我們來(lái)計(jì)算nums數(shù)組的前綴和數(shù)組arr，arr[i] = arr[i-1] + nums[i]
第一個(gè)元素由于沒(méi)有前綴所以只能是nums[0],也就是2?
?第二個(gè)元素就等于arr[1] = arr[0] + nums[1]
?
?
?
?我們得到的nums的前綴和數(shù)組就為 arr = [2，6，12，13，17]
作用：
那么我們得到這個(gè)前綴和數(shù)組到底有什么用呢？
有了前綴和數(shù)組我們就可以方便的計(jì)算出，一個(gè)數(shù)組的區(qū)間之內(nèi)的和，例如我們要求出nums[2]~nums[4] 的和。
nums[2]~nums[4] =nums[2] + nums[3] +nums[4] =? arr[4] - arr[1] = 11
可以直接用前綴和數(shù)組中的兩個(gè)元素求出，不用再進(jìn)行相加操作。這樣可以有效的減少我們的重復(fù)計(jì)算。
代碼為：public int[] prefix(int[] nums) { int[] prefix = new int[nums.length]; prefix[0] = nums[0]; for (int i = 1; i < nums.length; ++i) { prefix[i] = prefix[i - 1] + nums[i]; } return prefix; }
1.題目要求我們找到該數(shù)組中和為?k?的連續(xù)子數(shù)組的個(gè)數(shù)，我們可以先計(jì)算出數(shù)組的前綴和。
2.然后我們利用兩個(gè)for循環(huán)遍歷整個(gè)原數(shù)組，枚舉求出各個(gè)區(qū)間的和，若和等于k，則answer加一，注意這里，如果區(qū)間為[0,n]時(shí)，也就是左區(qū)間為0時(shí)，區(qū)間和[0,n] 就等于?arr[n],這個(gè)情況比較特殊所以我們要單獨(dú)計(jì)算。最后返回answer即可。
代碼實(shí)現(xiàn)
class Solution {
public int subarraySum(int[] nums, int k) {
int[] sum = new int[nums.length];
sum[0] = nums[0];
for(int i = 1; i < nums.length; i++){
sum[i] = sum[i-1] + nums[i];
}
int answer = 0;
for(int i = 0; i < nums.length; i++){
if(sum[i] == k){
answer++;
}
for(int j = i + 1; j < nums.length; j++){
if( sum[j] - sum[i] == k){
answer ++;
}
}
}
return answer;
}
}測(cè)試結(jié)果
?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-606889.html
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-606889.html
到了這里，關(guān)于Leetcode-每日一題【劍指 Offer II 010. 和為 k 的子數(shù)組】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
