寻找数组中和为0的子数组

Question

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 here
        map<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;
    }
};

当数据个数比较多时报错

Answer 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 here
        map<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 here
        map<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;
    }
};

Answer 2

排序，开始遍历，0-arr[i]，二分这个数。

Answer 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>();
    }
};