Description
Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not 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
Solutions
Solution 1: Hash Table + Prefix Sum
We can use a hash table d to record the first occurrence index of each prefix sum in the array nums, initializing d[0] = -1. Additionally, we define a variable s to keep track of the current prefix sum.
Next, we iterate through the array nums. For the current number nums[i], we update the prefix sum s = s + nums[i]. If s - k exists in the hash table d, let j = d[s - k], then the length of the subarray that ends at nums[i] and satisfies the condition is i - j. We use a variable ans to maintain the length of the longest subarray that satisfies the condition. After that, if s does not exist in the hash table, we record s and its corresponding index i by setting d[s] = i. Otherwise, we do not update d[s]. It is important to note that there may be multiple positions i with the same value of s, so we only record the smallest i to ensure the subarray length is the longest.
After the iteration ends, we return ans.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
d = {0: -1}
ans = s = 0
for i, x in enumerate(nums):
s += x
if s - k in d:
ans = max(ans, i - d[s - k])
if s not in d:
d[s] = i
return ans(code-box)
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
Map<Long, Integer> d = new HashMap<>();
d.put(0L, -1);
int ans = 0;
long s = 0;
for (int i = 0; i < nums.length; ++i) {
s += nums[i];
ans = Math.max(ans, i - d.getOrDefault(s - k, i));
d.putIfAbsent(s, i);
}
return ans;
}
}(code-box)
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<long long, int> d{{0, -1}};
int ans = 0;
long long s = 0;
for (int i = 0; i < nums.size(); ++i) {
s += nums[i];
if (d.count(s - k)) {
ans = max(ans, i - d[s - k]);
}
if (!d.count(s)) {
d[s] = i;
}
}
return ans;
}
};(code-box)
func maxSubArrayLen(nums []int, k int) (ans int) {
d := map[int]int{0: -1}
s := 0
for i, x := range nums {
s += x
if j, ok := d[s-k]; ok && ans < i-j {
ans = i - j
}
if _, ok := d[s]; !ok {
d[s] = i
}
}
return
}(code-box)
function maxSubArrayLen(nums: number[], k: number): number {
const d: Map<number, number> = new Map();
d.set(0, -1);
let ans = 0;
let s = 0;
for (let i = 0; i < nums.length; ++i) {
s += nums[i];
if (d.has(s - k)) {
ans = Math.max(ans, i - d.get(s - k)!);
}
if (!d.has(s)) {
d.set(s, i);
}
}
return ans;
}(code-box)
use std::collections::HashMap;
impl Solution {
pub fn max_sub_array_len(nums: Vec<i32>, k: i32) -> i32 {
let mut d = HashMap::new();
d.insert(0, -1);
let mut ans = 0;
let mut s = 0;
for (i, &x) in nums.iter().enumerate() {
s += x;
if let Some(&j) = d.get(&(s - k)) {
ans = ans.max((i as i32) - j);
}
d.entry(s).or_insert(i as i32);
}
ans
}
}(code-box)
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxSubArrayLen = function (nums, k) {
const d = new Map();
d.set(0, -1);
let ans = 0;
let s = 0;
for (let i = 0; i < nums.length; ++i) {
s += nums[i];
if (d.has(s - k)) {
ans = Math.max(ans, i - d.get(s - k));
}
if (!d.has(s)) {
d.set(s, i);
}
}
return ans;
};(code-box)
public class Solution {
public int MaxSubArrayLen(int[] nums, int k) {
var d = new Dictionary<int, int>();
d[0] = -1;
int ans = 0;
int s = 0;
for (int i = 0; i < nums.Length; i++) {
s += nums[i];
if (d.ContainsKey(s - k)) {
ans = Math.Max(ans, i - d[s - k]);
}
if (!d.ContainsKey(s)) {
d[s] = i;
}
}
return ans;
}
}(code-box)
