c++ - 寻找数组中和为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

雷雷