資訊專欄INFORMATION COLUMN
摘要：用記錄數(shù)組每一位之前的包含當(dāng)前位所有元素之和。若有重復(fù)的出現(xiàn)，說(shuō)明之前的對(duì)應(yīng)的元素的下一位到當(dāng)前對(duì)應(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.
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 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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65734.html
摘要：做一個(gè)窗口，滿足的左界到右界的距離最小值為所求。循環(huán)的約束條件要注意，不要遺漏不能超過(guò)的長(zhǎng)度，但可以等于，因?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...
摘要：這是一道簡(jiǎn)單的動(dòng)規(guī)題目，同步更新數(shù)組解決了為負(fù)數(shù)的問(wèn)題。即使是求最小乘積子序列，也可以通過(guò)取和的最小值獲得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...
摘要：動(dòng)態(tài)規(guī)劃法用表示最大子數(shù)組的結(jié)束下標(biāo)為的情形，則對(duì)于，有這樣就有了一個(gè)子結(jié)構(gòu)，對(duì)于初始情形，遍歷就能得到這個(gè)數(shù)組，其最大者即可最大子數(shù)組的和。動(dòng)態(tài)規(guī)劃法想法巧妙，運(yùn)行效率也高，但是沒(méi)有普遍的適用性。 問(wèn)題簡(jiǎn)介 ??本文將介紹計(jì)算機(jī)算法中的經(jīng)典問(wèn)題——最大子數(shù)組問(wèn)題（maximum subarray problem）。所謂的最大子數(shù)組問(wèn)題，指的是：給定一個(gè)數(shù)組A，尋找A的和最大的非空連續(xù)...
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...
閱讀 6457·2021-11-22 15:32
閱讀 945·2021-11-11 16:54
閱讀 3254·2021-10-13 09:40
閱讀 2251·2021-09-03 10:35
閱讀 1924·2021-08-09 13:47
閱讀 1943·2019-08-30 15:55
閱讀 2002·2019-08-30 15:43
閱讀 2519·2019-08-29 17:06
