[LintCode] Subarray Sum

shaonbean 發布于2019-08-14 15:24 / 3001人閱讀

摘要：用記錄數組每一位之前的包含當前位所有元素之和。若有重復的出現，說明之前的對應的元素的下一位到當前對應的第個元素之間所有元素和為，即為所求的子序列。

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記錄數組nums每一位index之前的（包含當前位）所有元素之和。若有重復的sum出現，說明之前的sum對應的元素的下一位map.get(sum)+1到當前sum對應的第i個元素之間所有元素和為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;
    }
}

GPU云服務器云服務器 subarray LintCode LintCode134_LRU sum

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65734.html

[LintCode] Minimum Size Subarray Sum

摘要：做一個窗口，滿足的左界到右界的距離最小值為所求。循環的約束條件要注意，不要遺漏不能超過的長度，但可以等于，因為存在所有元素之和為的極端情況。在時，先更新窗口為當前循環后的最小值，減去最左元素，指針后移。 Problem Given an array of n positive integers and a positive integer s, find the minimal len...

hyuan 2019-08-14 15:16 評論0 收藏0
[LintCode/LeetCode] Maximum Product Subarray

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

meteor199 2019-08-14 15:21 評論0 收藏0
動態規劃法（八）最大子數組問題（maximum subarray problem）

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

jzman 2019-07-30 16:46 評論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 2019-08-15 15:47 評論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