题目：
给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
给出[-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].
解题：
纯暴力，时间超时
Java程序：
public class Solution { /** * @param nums: A list of integers * @return: A list of integers includes the index of the first number * and the index of the last number */ public ArrayList<Integer> subarraySum(int[] nums) { // write your code here ArrayList<Integer> result = new ArrayList<Integer>(); for(int i=0;i<nums.length;i++){ if(nums[i]==0){ result.add(i); result.add(i); return result; } for(int j=i+1;j<nums.length;j++){ int sum = 0; for(int k = i;k<=j;k++){ sum+=nums[k]; } if(sum==0){ result.add(i); result.add(j); return result; } } } return result; } }
时间复杂度：O(n3)
参考编程之美，时间复杂度降为：O(n2)，这个转换其实很简单，但是有可能你就不知道
Java程序：
public class Solution { /** * @param nums: A list of integers * @return: A list of integers includes the index of the first number * and the index of the last number */ public ArrayList<Integer> subarraySum(int[] nums) { // write your code here ArrayList<Integer> result = new ArrayList<Integer>(); for(int i=0;i<nums.length;i++){ if(nums[i]==0){ result.add(i); result.add(i); return result; } int sum = 0; for(int j=i;j<nums.length;j++){ sum+=nums[j]; if(sum==0){ result.add(i); result.add(j); return result; } } } return result; } }
总耗时: 4127 ms
转化成Python程序：
class Solution: """ @param nums: A list of integers @return: A list of integers includes the index of the first number and the index of the last number """ def subarraySum(self, nums): # write your code here numslen = len(nums) for i in range(numslen): sum = 0 for j in range(i,numslen): sum+=nums[j] if sum==0: return [i,j]
总耗时: 974 ms
时间复杂度，也可以降到O(n)
这里利用到HashMap，从nums[0] 到nums[nums.length-1]的和，都添加到HashMap中，在这个求和的过程中回出现下面情况:
sum0->i = sum0->j
这里就说明sum(i+1)->j的和是0
这样时间复杂度就是O(n)
Java程序：
public class Solution { /** * @param nums: A list of integers * @return: A list of integers includes the index of the first number * and the index of the last number */ public ArrayList<Integer> subarraySum(int[] nums) { // write your code here int numslen = nums.length; ArrayList<Integer> result = new ArrayList<Integer>(); HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); map.put(0,-1); int sum = 0; for(int i=0;i<numslen;i++){ sum+=nums[i]; if(map.containsKey(sum)){ result.add(map.get(sum) + 1); result.add(i); return result; } map.put(sum,i); } return result; } }
总耗时: 4520 ms
Python程序：
class Solution: """ @param nums: A list of integers @return: A list of integers includes the index of the first number and the index of the last number """ def subarraySum(self, nums): # write your code here numslen = len(nums) d = {0:-1} sum = 0 for i in range(numslen): sum = sum + nums[i] if sum in d: return [d.get(sum) + 1,i] d[sum] = i
总耗时: 1361 ms
lintcode 容易题：Subarray Sum 子数组之和
原文：http://www.cnblogs.com/theskulls/p/4872718.html
