国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] Maximum Size Subarray Sum Equals k

MudOnTire / 3303人閱讀

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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/69271.html

相關(guān)文章

  • [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 評論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 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論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 評論0 收藏0

  • [Leetcode] Maximum Subarray 子序列最大和

    摘要：最新更新請見原題鏈接動態(tài)規(guī)劃復雜度時間空間思路這是一道非常典型的動態(tài)規(guī)劃題，為了求整個字符串最大的子序列和，我們將先求較小的字符串的最大子序列和。而最大子序列和的算法和上個解法還是一樣的。 Maximum Subarray 最新更新請見：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

    summerpxy 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<