資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律研究C++ 中的子陣列總和等於 K
假設我們有一個整數陣列和一個整數 k，我們需要找出總和與 k 相同的所有連續子陣列的總數。因此，如果 nums 陣列為 [1, 1, 1] 並且 k 為 2，那麼輸出將為 2。
為了解決這個問題，我們將執行以下步驟−
- 定義一個名為 sums、temp := 0、sums[0] := 1 和 ans := 0 的對映
- 對於 i 在陣列的大小的範圍內
- temp := temp + n[i]
- 如果 sums 具有 k – temp，則
- ans := ans + sums[k - temp]
- 將 sums[-temp] 的值增加 1
- 返回 ans
示例（C++）
我們來看看以下實現，以獲得更好的理解−
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& n, int k) {
unordered_map <int, int> sums;
int temp = 0;
sums[0] = 1;
int ans =0;
for(int i =0;i<n.size();i++){
temp+= n[i];
if(sums.find(k-temp)!=sums.end()){
ans += sums[k-temp];
}
sums[-temp]++;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,1,1};
cout << (ob.subarraySum(v, 2));
}輸入
[1,1,1] 2
輸出
2
更新日期：2020 年 4 月 29 日
695 次檢視
廣告