[LeetCode] 325.最大サイズのサブアレイの合計はkに等しく、kは最長のサブアレイに等しい
325 Maximum Size Subarray Sum Equals K
与えられた配列 nums と目標値 に 、合計するサブ配列の最大長を見つけます に 。存在しない場合は、代わりに0を返します。
例1：
与えられた nums = [1, -1, 5, -2, 3]、 に = 3、 4を返します。 （サブ配列[1, -1, 5, -2]の合計は3であり、最長であるため）
例2：
与えられた nums = [-2, -1, 2, 1]、 に = 1、 2を返します。 （サブ配列[-1, 2]の合計は1であり、最長であるため）
ファローアップ：
O（ n ）時間？
配列をターゲット値とkにNumsし、サブ配列と最大長kを見つけ、要件O（n）の時間計算量がない場合は0を返します。
解決策1：すべての組み合わせのダブルポインター、ダブルループ計算、およびkの場合は、max_lenを更新するかどうかを決定します。時間計算量が高い、TLE
解決策：これまでのすべての配列の変数レコードcur_sumを使用して配列をループし、kがmax_lenを更新する場合は、累積レコードを使用してインデックスをマップします。ヒント：最長の配列を探しているため、最初にインデックスがその場所に表示された後、記録されない場合は、一度だけ記録します。ハッシュマップcur_sumで、記録内の現在の位置がハッシュマップcur_sumを削除することを示している場合-kがインデックスkに等しい場合は、2つの差分max_lenのインデックスを更新します。
Java：
public int maxSubArrayLen(int[] nums, int k) { HashMap map = new HashMap() int max = 0 int sum=0 for(int i=0 iPython：時間：O（n）、スペース：O（n）
class Solution(object): def maxSubArrayLen(self, nums, k): ''' :type nums: List[int] :type k: int :rtype: int ''' sums = {} cur_sum, max_len = 0, 0 for i in xrange(len(nums)): cur_sum += nums[i] if cur_sum == k: max_len = i + 1 elif cur_sum - k in sums: max_len = max(max_len, i - sums[cur_sum - k]) if cur_sum not in sums: sums[cur_sum] = i # Only keep the smallest index. return max_len Python：ここで
class Solution(): def maxSubarry(self, nums, k): m = {0: -1} sm = 0 for i in range(len(nums)): sm += nums[i] if sm not in m: m[sm] = i if sm - k in m: max_len = max(max_len, i - m[sm-k]) return max_len C ++：
class Solution { public: int maxSubArrayLen(vector& nums, int k) { int sum = 0, res = 0 unordered_map m for (int i = 0 i 同様のトピック：
[LeetCode] 209.最小最小サイズサブ配列サブ配列の合計、および
[LeetCode] 560。サブ配列の合計はKサブ配列とKに等しい
範囲合計クエリ-不変