Блог

Поскольку я пытался решить эту проблему с интервью: найдите сумму непрерывного элемента в массиве, которая равна целевому числу, поэтому я придумал следующий код. Однако я действительно не понимаю, почему у него какая-то проблема с выделением памяти. Вот ссылка на полный код. когда я попытался вставить второй элемент currSum в набор и карту, у него появится сообщение об ошибке, например «память заблокирована после конца выделенного блока». Не установлено, карта динамически выделяется для вставки? Я действительно не понимаю, почему это работает не так, как я думаю.

Я также вставляю полный код здесь:

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

Ошибка в этой строке:

 int* currSum= new int(sizeArr 1);
  

Эта строка получает единицу int и инициализирует ее значением sizeArr 1 . Вы, вероятно, имели в виду:

 int* currSum= new int[sizeArr 1];
  

Это приведет к получению блока sizeArr 1 элементов типа int . Кроме того, вам придется изменить строку delete currSum; на delete [] currSum; быть.

С другой стороны, я бы посоветовал не управлять памятью вручную, а использовать стандартный контейнер, например:

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

В основном это будет замена на месте для вашей текущей реализации, и она будет автоматически управлять памятью.

Что касается реализации, я считаю, что вы действительно можете сделать это без какой-либо дополнительной памяти в O (N), накапливая начальный индекс, конечный индекс и сумму значений в трех переменных во время итерации. Пока накопленное значение меньше целевого, увеличьте конечный индекс и добавьте значение. Когда накопленное значение становится выше целевого, увеличьте начальный индекс и уменьшите накопленное значение на эту величину.

вы написали

 int* currSum= new int(sizeArr 1);
  

вы, вероятно, имели в виду

 int* currSum= new int[sizeArr 1];