[LeetCode] Maximum Size Subarray Sum Equals k

MudOnTire 发布于2019-08-15 15:47 / 3305人阅读

Problem

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.

Note

The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Examples

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?

Solution

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map map = new HashMap<>();
        int max = 0, sum = 0;
        //this is the crucial step... if the subarray starts from index 0, 
        //we need to count an extra 1 as it is one less than the actual length
        map.put(0, -1); 
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum-k)) {
                //sum-k means... the preSum satisfies: sum-preSum=k
                //so lets get "i-preSum_index" and compare with existing max length
                max = Math.max(max, i-map.get(sum-k));
            }
            //if map already has current sum, we would definitely use the earlier index 
            //to get the larger length, right?
            if (!map.containsKey(sum)) map.put(sum, i);
        }
        return max;
    }
}

云服务器 GPU云服务器 subarray Maximum LeetCode key_buffer_size

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69271.html

[LeetCode] 560. Subarray Sum Equals K

Problem Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note:The length o...

ccj659 2019-08-16 13:30 评论0 收藏0
[LeetCode] 689. Maximum Sum of 3 Non-Overlapping S

摘要： Problem In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size k, and we want to maximize the sum of all 3*k entries. R...

dailybird 2019-08-16 13:30 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] 523. Continuous Subarray Sum

Problem Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sum...

stackfing 2019-08-16 13:46 评论0 收藏0
[Leetcode] Maximum Subarray 子序列最大和

摘要：最新更新请见原题链接动态规划复杂度时间空间思路这是一道非常典型的动态规划题，为了求整个字符串最大的子序列和，我们将先求较小的字符串的最大子序列和。而最大子序列和的算法和上个解法还是一样的。 Maximum Subarray 最新更新请见：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

summerpxy 2019-08-14 16:11 评论0 收藏0