stl 映射，设置错误：内存在分配块的末尾被破坏

Question

当我试图解决这个面试问题时：找到数组中连续元素的总和等于目标数字，所以我想出了以下代码。但是，我真的不明白为什么它有一些内存分配问题。这是完整代码的链接。当我尝试将 currSum 的第二个元素插入集合和映射时，它会出现一些错误消息，例如“内存破坏了分配块的末尾”。不是设置了，map动态分配用于插入吗？我真的不明白为什么它没有像我想象的那样工作。

我还将完整的代码粘贴在这里：

        #include <map>
        #include <set>
        #include <iostream>
        using namespace std;

        void print_array(int arr[], int start, int end)
        {
            for(int i=start;i<=end;i++)
                cout<<arr[i]<<" ";
            cout<<endl;
        }

        //given an array, find the continous sum of the array which is a target number
        void findTargetSum(int arr[], int target, int sizeArr)
        {
            map<int, int> valIdxMap;
            set<int> prevSet;
            int* currSum= new int(sizeArr+1);
            currSum[0]=0;   
            for(int i=1;i<=sizeArr;i++)
            {
                currSum[i]=currSum[i-1]+arr[i-1];
            }

            //now the problem is to find two elements i, j in array currSum,where currSum[j]-currSum[i]=target && j>i
            for(int i=0; i<=sizeArr;i++)
            {
                int tmp=currSum[i]-target;
                set<int>::iterator iter=prevSet.find(tmp);
                if (iter !=prevSet.end())
                {
                    cout<<"located one range of array elements with sum to"<<target<<endl;
                    int startIdx=valIdxMap[*iter];
                    print_array(arr,startIdx,i-1);
                }
                else
                {
                    prevSet.insert(currSum[i]);
                    valIdxMap.insert(make_pair(currSum[i],i));
                }
            }
            delete currSum;
        }

        void testfindTargetSum()
        {
            int tst_arr[]={2,4,5,-1,3,8};
            int target=11;
            findTargetSum(tst_arr,11,6);
        }

        int main()
        {
           testfindTargetSum();
           return 1;
        }

Answer 1

错误出现在这一行中：

int* currSum= new int(sizeArr+1);

该行获取单个 int 并将其初始化为值 sizeArr+1。您可能的意思是：

int* currSum= new int[sizeArr+1];

这将获取一个 int 类型的 sizeArr+1 元素块。此外，您还必须将 delete currSum; 行更改为 delete [] currSum;。

另一方面，我的建议是不要手动管理内存，而是使用标准容器，例如：

std::vector<int> currSum( sizeArr+1 );

基本上将是当前实现的就地替换，并且它将自动管理内存。

在实现时，我相信您实际上可以通过在迭代时累积三个变量中的开始索引、结束索引和值的总和，在 O(N) 中无需任何额外内存即可完成此操作。当累加值小于目标值时，增加结束索引并添加该值。当累计值高于目标值时，增加起始索引并按该量减少累计值。

Answer 2

你写的

int* currSum= new int(sizeArr+1);

可能是你的意思

int* currSum= new int[sizeArr+1];