LC: 325. Maximum Size Subarray Sum Equals k
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
325. Maximum Size Subarray Sum Equals k
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
Example 1:
Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.Example 2:
Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.Constraints:
1 <= nums.length <= 2 * 105-104 <= nums[i] <= 104-109 <= k <= 109
Maximum Size Subarray Sum Equals k
The Essence:
Ein Subarray der Summe k entspricht dem Subarray, die die Folgenden einhält: Die Summe aller Zahlen bis zu einem bestimmten Index i entspricht einer Summe s. Wenn wir k von s subtrahieren, erhalten wir eine andere Summe. Wenn diese Summe bei einem vorherigen Index j begegnet ist, ist die Summe des Subarrays im Intervall [i,j] gleich k.
Beispiel: Es seien ein Array [7, 1, -2, 5, -1, 3] und k = 3. Die Summe bei dem Index i = 4 ist (7+1+(-2)+5+(-1)) = 10. Wenn wir k davon subtrahieren, erhalten wir 7. Wir haben zuvor die Summe 7 bei dem Index j = 0 gesehen. Daher ergibt sich aus i-j = 4 die maximale Länge 4
Details:
Die Präfixsumme bei einem Index kann als der Schlüssel einer Hashtabelle oder eines Arrays sein. Man soll auch annehmen, dass vor allen Indizes die Summe 0 ist.
Solution(s) and Further Explanation:
Further explanation and implementation can be found here:
Default Code:
Last updated