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

資訊專欄INFORMATION COLUMN

[LintCode] Subarray Sum

shaonbean / 3008人閱讀

摘要：用記錄數(shù)組每一位之前的包含當(dāng)前位所有元素之和。若有重復(fù)的出現(xiàn)，說明之前的對應(yīng)的元素的下一位到當(dāng)前對應(yīng)的第個(gè)元素之間所有元素和為，即為所求的子序列。

Problem

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Notice

There is at least one subarray that it"s sum equals to zero.

Example

Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Note

用HashMap記錄數(shù)組nums每一位index之前的（包含當(dāng)前位）所有元素之和。若有重復(fù)的sum出現(xiàn)，說明之前的sum對應(yīng)的元素的下一位map.get(sum)+1到當(dāng)前sum對應(yīng)的第i個(gè)元素之間所有元素和為0，即為所求的子序列。

Solution 
public class Solution {
    public ArrayList subarraySum(int[] nums) {
        int n = nums.length;
        ArrayList res = new ArrayList();
        Map map = new HashMap();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                res.add(map.get(sum)+1);
                res.add(i);
                return res;
            }
            else map.put(sum, i);
        }
        return res;
    }
}

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

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

相關(guān)文章

  • [LintCode] Minimum Size Subarray Sum

    摘要：做一個(gè)窗口，滿足的左界到右界的距離最小值為所求。循環(huán)的約束條件要注意，不要遺漏不能超過的長度，但可以等于，因?yàn)榇嬖谒性刂蜑榈臉O端情況。在時(shí)，先更新窗口為當(dāng)前循環(huán)后的最小值，減去最左元素，指針后移。 Problem Given an array of n positive integers and a positive integer s, find the minimal len...

    hyuan 評論0 收藏0

  • [LintCode/LeetCode] Maximum Product Subarray

    摘要：這是一道簡單的動規(guī)題目，同步更新數(shù)組解決了為負(fù)數(shù)的問題。即使是求最小乘積子序列，也可以通過取和的最小值獲得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...

    meteor199 評論0 收藏0

  • 動態(tài)規(guī)劃法（八）最大子數(shù)組問題（maximum subarray problem）

    摘要：動態(tài)規(guī)劃法用表示最大子數(shù)組的結(jié)束下標(biāo)為的情形，則對于，有這樣就有了一個(gè)子結(jié)構(gòu)，對于初始情形，遍歷就能得到這個(gè)數(shù)組，其最大者即可最大子數(shù)組的和。動態(tài)規(guī)劃法想法巧妙，運(yùn)行效率也高，但是沒有普遍的適用性。 問題簡介 ??本文將介紹計(jì)算機(jī)算法中的經(jīng)典問題——最大子數(shù)組問題（maximum subarray problem）。所謂的最大子數(shù)組問題，指的是：給定一個(gè)數(shù)組A，尋找A的和最大的非空連續(xù)...

    jzman 評論0 收藏0

  • [LeetCode] Maximum Size Subarray Sum Equals k

    Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...

    MudOnTire 評論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

發(fā)表評論

0條評論

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