Lintcode:Subaray Sum解題レポート
6495 ワード
Subarray Sum
原題リンク:http://lintcode.com/zh-cn/problem/subarray-sum/#
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.
サンプル
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].
ラベルExpand
SOLUTION 1:
O(N)の解法がある.Mapを使用してindex,sumの値を記録します.2つのindexのsum相が同時に遭遇すると,index 1+1からindex 2までが解であることを示す.
注:index=-1を仮想ノードとして追加します.これによりindex 1=0の解を記録することができる.
空間複雑度:O(N)
View Code
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/array/SubarraySum.java
原題リンク:http://lintcode.com/zh-cn/problem/subarray-sum/#
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.
サンプル
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].
ラベルExpand
SOLUTION 1:
O(N)の解法がある.Mapを使用してindex,sumの値を記録します.2つのindexのsum相が同時に遭遇すると,index 1+1からindex 2までが解であることを示す.
注:index=-1を仮想ノードとして追加します.これによりindex 1=0の解を記録することができる.
空間複雑度:O(N)
1 public class Solution {
2 /**
3 * @param nums: A list of integers
4 * @return: A list of integers includes the index of the first number
5 * and the index of the last number
6 */
7 public ArrayList<Integer> subarraySum(int[] nums) {
8 // write your code here
9
10 int len = nums.length;
11
12 ArrayList<Integer> ret = new ArrayList<Integer>();
13
14 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
15
16 // We set the index -1 sum to be 0 to let us more convient to count.
17 map.put(0, -1);
18
19 int sum = 0;
20 for (int i = 0; i < len; i++) {
21 sum += nums[i];
22
23 if (map.containsKey(sum)) {
24 // For example:
25 // -3 1 2 -3 4
26 // SUM: 0 -3 -2 0 -3 1
27 // then we got the solution is : 0 - 2
28 ret.add(map.get(sum) + 1);
29 ret.add(i);
30 return ret;
31 }
32
33 // Store the key:value of sum:index.
34 map.put(sum, i);
35 }
36
37 return ret;
38 }
39 }
View Code
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/array/SubarraySum.java