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

Looking at the idea of ​​the algorithm of the questioner, it should be through summation. When two identical sums appear, it can be judged that the sum of the consecutive sub-arrays in the middle is 0. I have modified my answer. .
AC code, I only modified one serial number and changed it to a tot auxiliary summation. It can be passed:

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

The questioner silently changed the question ==, QAQ, without telling me the question with the serial number 0, because there is no mark for the position with the serial number 0 in your map, I only added one this time The position of the array with sequence number 0.
AC code, the questioner doesn’t want to talk to me = =:

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

Sort, start traversing, 0-arr[i], divide this number into two.

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