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

資訊專欄INFORMATION COLUMN

[LeetCode] Maximum Size Subarray Sum Equals k

MudOnTire / 3310人閱讀

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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.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 評(píng)論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 評(píng)論0 收藏0

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

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

    leo108 評(píng)論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 評(píng)論0 收藏0

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

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

    summerpxy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<