问题描述
class Solution {public: /** * @param nums: A list of integers * @retu rn: 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 heremap<int, int> mymap; mymap[0] = -1;vector<int> result;if( !nums.size() ) return result;if( nums[0] == 0 ){ result.push_back( 0 ); result.push_back( 0 ); return result;}int i = 0;for( i = 1; i < nums.size(); i++ ){ nums[i] += nums[ i - 1 ]; if( mymap.find( nums[i] ) == mymap.end() )mymap[nums[i]] = i; else {result.push_back( mymap[nums[i]] + 1 );result.push_back( i ); return result; }} return result; }};
当数据个数比较多时报错
问题解答
回答1：看题主的算法的思想，应该是通过求和，当出现两个相同的和时，就可以判断中间连续子数组和为0.我已修改了回答。。AC代码，我只修改了一个序号,改成一个tot辅助求和，可以过啊：
class Solution {public: /** * @param nums: A list of integers * @retu rn: 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 heremap<int, int> mymap; mymap[0] = -1;vector<int> result;if( !nums.size() ) return result;if( nums[0] == 0 ){ result.push_back( 0 ); result.push_back( 0 ); return result;}int i = 0;int tot = 0;for( i = 0; i < nums.size(); i++ ){ tot += nums[i]; if( mymap.find( tot ) == mymap.end() )mymap[tot] = i; else {result.push_back( mymap[tot] + 1 );result.push_back( i ); return result; }} return result; }};
题主默默的把问题改了 = = ，QAQ， 都不告诉下我，序号为0的问题， 因为你map里面没有序号为0的那个位置的标记吧，我这次只加了一个序号为0的数组的位置。AC代码，题主都不愿理我了= =：
class Solution {public: /** * @param nums: A list of integers * @retu rn: 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 heremap<int, int> mymap; mymap[0] = -1;vector<int> result;if( !nums.size() ) return result;if( nums[0] == 0 ){ result.push_back( 0 ); result.push_back( 0 ); return result;}mymap[nums[0]] = 0;int i = 0;for( i = 1; i < nums.size(); i++ ){ nums[i] += nums[ i - 1 ]; if( mymap.find( nums[i] ) == mymap.end() )mymap[nums[i]] = i; else {result.push_back( mymap[nums[i]] + 1 );result.push_back( i ); return result; }} return result; }};
排序，开始遍历，0-arr[i]，二分这个数。
回答3：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){int length = nums.size();for (int i = 0; i < length; i++) { int count = 0; for (int j = i; j < length; j++) {count += nums[j];if (count == 0) { vector<int> r; r.push_back(i); r.push_back(j); return r;} }}return vector<int>(); }};
