給定一個整數數組和一個整數?k，你需要找到該數組中和為?k?的連續的子數組的個數。

示例 1 :

輸入:nums = [1,1,1], k = 2 輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。

說明 :

數組的長度為 [1, 20,000]。

數組中元素的范圍是 [-1000, 1000] ，且整數?k?的范圍是?[-1e7, 1e7]。

?

方法一： 暴力索引

class Solution { public:int subarraySum(vector<int>& nums, int k) {int result = 0;int n = nums.size();int* sum = new int[n];sum[0] = nums[0];for(int i=1;i<n;++i){sum[i] = sum[i-1]+nums[i];}int temp = 0;for(int i=0;i<n;++i){int i_t = i-1;for(int j=i;j<n;++j){if(i_t==-1)temp=sum[j];elsetemp = sum[j]-sum[i_t];if(temp==k)result++;}}return result;} };

方法二：

反向思維

class Solution { public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> map;int n = nums.size();map[0] = 1;int sum = 0;int result = 0;for(int i=0;i<n;++i){sum += nums[i];if(map.find(sum-k)!=map.end())result += map[sum-k];map[sum]++;}return result;} };

?

總結

以上是生活随笔為你收集整理的和为K的子数组—leetcode560的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。