資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的連續子陣列和
假設我們有一個非負數列表和一個目標整數 k，我們必須編寫一個函式來檢查陣列是否有一個大小至少為 2 的連續子陣列，其總和是 k 的倍數，總和等於 n*k，其中 n 也是一個整數。因此，如果輸入類似於 [23,2,4,6,7]，並且 k = 6，則結果將為 True，因為 [2,4] 是大小為 2 的連續子陣列，並且總和為 6。
為了解決這個問題，我們將按照以下步驟進行操作 −
- 建立一個對映 m，設定 m[0] := -1，sum := 0，n := nums 陣列的大小
- 對於 i 在範圍 0 到 n – 1 之間
- sum := sum + nums[i]
- 如果 k 為非零，則 sum := sum mod k
- 如果 m 具有 sum，並且 i – m[sum] >= 2，則返回 true
- 如果 m 沒有 sum，則設定 m[sum] := i
- 返回 false
讓我們看看以下實現以獲得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> m;
m[0] = -1;
int sum = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
sum += nums[i];
if(k)
sum %= k;
if(m.count(sum) && i - m[sum] >= 2){
return true;
}
if(!m.count(sum)) m[sum] = i;
}
return false;
}
};
main(){
vector<int> v = {23,2,4,6,7};
Solution ob;
cout << (ob.checkSubarraySum(v, 6));
}輸入
[23,2,4,6,7] 6
輸出
1
更新於: 02-2020 年 5 月
1K+ 檢視次數
廣告