[LintCode] Subarray Sum

shaonbean 发布于2019-08-14 15:24 / 2924人阅读

摘要：用记录数组每一位之前的包含当前位所有元素之和。若有重复的出现，说明之前的对应的元素的下一位到当前对应的第个元素之间所有元素和为，即为所求的子序列。

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

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

转载请注明本文地址：https://www.ucloud.cn/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