題目：

給定一個整數數組，找到和為零的子數組。你的代碼應該返回滿足要求的子數組的起始位置和結束位置。

樣例

給出[-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].

解題思路：

依次求數組的前綴和，同時執行如下操作：

假定當前位置是i，查找i之前位置的前綴和，是否存在j位置，使得，j位置的前綴和 等于 i位置的前綴和。

若有，則j 到 i 之間的區間數的和為0.

直到遍歷完整個數組。

時間復雜度O(n)，空間復雜度O(n).

實現代碼：

class Solution { public:/*** @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*/vector<int> subarraySum(vector<int> nums){// write your code hereint sum = 0;vector<int> ret;unordered_map<int, int> map;map[0] = -1;for(int i=0; i<nums.size();i++){sum += nums[i];if(map.find(sum) != map.end()){ret.push_back(map[sum] +1);ret.push_back(i);return ret;}map[sum] = i;}return ret;} };

總結

以上是生活随笔為你收集整理的LintCode_138——子数组和为零的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。