資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中和 k 相等的子陣列最大大小
假設我們有一個名為 nums 的陣列和一個目標值 k，我們需要找到和為 k 的子陣列的最大長度。如果沒有，則返回 0。
因此，如果輸入類似於 nums = [1, -1, 5, -2, 3]，k = 3，則輸出將為 4，因為子陣列 [1, - 1, 5, -2] 的和為 3 並且是最長的。
為了解決這個問題，我們將遵循以下步驟：
ret := 0
定義一個對映 m
n := nums 的大小
temp := 0, m[0] := -1
初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
temp := temp + nums[i]
如果 (temp - k) 在 m 中，則：
ret := ret 和 i - m[temp - k] 的最大值
如果 temp 不在 m 中，則：
m[temp] := i
返回 ret
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSubArrayLen(vector<int<& nums, int k) {
int ret = 0;
unordered_map <int, int> m;
int n = nums.size();
int temp = 0;
m[0] = -1;
for(int i = 0; i < n; i++){
temp += nums[i];
if(m.count(temp - k)){
ret = max(ret, i - m[temp - k]);
}
if(!m.count(temp)){
m[temp] = i;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int< v = {1,-1,5,-2,3};
cout << (ob.maxSubArrayLen(v, 3));
}輸入
[1,-1,5,-2,3], 3
輸出
4
更新於: 2020-11-18
730 次檢視
廣告