Zero Sum Subarray

Question

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.

Example
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Note
There is at least one subarray that it's sum equals to zero.


题解2 - 比较子串和(TLE)

C++

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){
vector<int> result;

int curr_sum = 0;
vector<int> sum_i;
for (int i = 0; i != nums.size(); ++i) {
curr_sum += nums[i];

if (0 == curr_sum) {
result.push_back(0);
result.push_back(i);
return result;
}

vector<int>::iterator iter = find(sum_i.begin(), sum_i.end(), curr_sum);
if (iter != sum_i.end()) {
result.push_back(iter - sum_i.begin() + 1);
result.push_back(i);
return result;
}

sum_i.push_back(curr_sum);
}

return result;
}
};


题解3 - 哈希表

C++

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){
vector<int> result;
// curr_sum for the first item, index for the second item
map<int, int> hash;
hash[0] = 0;

int curr_sum = 0;
for (int i = 0; i != nums.size(); ++i) {
curr_sum += nums[i];
if (hash.find(curr_sum) != hash.end()) {
result.push_back(hash[curr_sum]);
result.push_back(i);
return result;
} else {
hash[curr_sum] = i + 1;
}
}

return result;
}
};


题解4 - 排序

C++

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){
vector<int> result;
if (nums.empty()) {
return result;
}

const int num_size = nums.size();
vector<pair<int, int> > sum_index(num_size + 1);
for (int i = 0; i != num_size; ++i) {
sum_index[i + 1].first = sum_index[i].first + nums[i];
sum_index[i + 1].second = i + 1;
}

sort(sum_index.begin(), sum_index.end());
for (int i = 1; i < num_size + 1; ++i) {
if (sum_index[i].first == sum_index[i - 1].first) {
result.push_back(sum_index[i - 1].second);
result.push_back(sum_index[i].second - 1);
return result;
}
}

return result;
}
};