摘要:用记录数组每一位之前的包含当前位所有元素之和。若有重复的出现,说明之前的对应的元素的下一位到当前对应的第个元素之间所有元素和为,即为所求的子序列。
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.
NoticeThere is at least one subarray that it"s sum equals to zero.
ExampleGiven [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].
Note用HashMap
public class Solution { public ArrayListsubarraySum(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; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65734.html
摘要:做一个窗口,满足的左界到右界的距离最小值为所求。循环的约束条件要注意,不要遗漏不能超过的长度,但可以等于,因为存在所有元素之和为的极端情况。在时,先更新窗口为当前循环后的最小值,减去最左元素,指针后移。 Problem Given an array of n positive integers and a positive integer s, find the minimal len...
摘要:这是一道简单的动规题目,同步更新数组解决了为负数的问题。即使是求最小乘积子序列,也可以通过取和的最小值获得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...
摘要:动态规划法用表示最大子数组的结束下标为的情形,则对于,有这样就有了一个子结构,对于初始情形,遍历就能得到这个数组,其最大者即可最大子数组的和。动态规划法想法巧妙,运行效率也高,但是没有普遍的适用性。 问题简介 本文将介绍计算机算法中的经典问题——最大子数组问题(maximum subarray problem)。所谓的最大子数组问题,指的是:给定一个数组A,寻找A的和最大的非空连续...
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 ...
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...
阅读 6052·2021-11-22 15:32
阅读 757·2021-11-11 16:54
阅读 3121·2021-10-13 09:40
阅读 2103·2021-09-03 10:35
阅读 1787·2021-08-09 13:47
阅读 1826·2019-08-30 15:55
阅读 1914·2019-08-30 15:43
阅读 2397·2019-08-29 17:06