Leetcode 325. Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Difficulty:Medium

Category:

Analyze

这道题给我们一个一维数组nums,让我们求和为k最大子数组,默认子数组必须连续,题目中提醒我们必须要在O(n)的时间复杂度完成.

Solution

该方案来自于博客文章:Maximum Size Subarray Sum Equals k 最大子数组之和为k

class Solution {
 public:
  int maxSubArrayLen(vector<int>& nums, int k) {
    // sum: 累加
    int sum = 0, res = 0;
    unordered_map<int, int> m; // [value -> lastindex]
    for (int i = 0; i < nums.size(); ++i) {
      sum += nums[i];
      //边累加边处理
      if (sum == k)
        res = i + 1;
      else if (m.count(sum - k))
        res = max(res, i - m[sum - k]);
      // Save the first index when we get the sum
      if (!m.count(sum)) m[sum] = i;
    }
    return res;
  }
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""