Runtime error. Tried a solution sorting the array and then looking for the sum using two moving indexes


  • 0
    M

    Hi, I posted a previous answer regarding this problem. I tried to resolve sorting the array and then finding the sums using two indexes, one at the front and another one at the end. I know this can be solved using a hash table but for the moment I'm trying this as well. Thing is, I get runtime error... don't know why. Help is very much appreciated. Thanks

    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            
            int index1, index2, a, b;
            vector<int> solution(2);
            
            //Sort
            for (int i=0; i<numbers.size(); i++)
            {
                int k = i;
                int x = numbers[i];
                for (int j=i+1; j<=numbers.size(); j++)
                {
                    if (numbers[j]<x)
                    {
                        k=j;
                        x=numbers[k];
                    }
                }
                numbers[k] = numbers[i];
                numbers[i]=x;
            }
            
            //Look for sum
            b=numbers.size();
            
            while (a<b) 
            {
                if (numbers[a] + numbers[b] > target)
                {
    				b--;
                }
    			else if (numbers[a] + numbers[b] < target)
    			{
    				a++;
    			}
    			else
    			{
    			    solution.push_back(a);
    			    solution.push_back(b);
    			    return solution;
    			}
            }
        }
    };

  • 0
    D

    brother you did not initialise the varible a.so it's taking garbage value.. and causing segmentation fault


  • 0
    M

    thanks!!! i didn't notice!


  • 0
    P

    Also output index would be based on the sorted index and actual problem would need original index so you might have to add another loop to find the original index.


  • 0
    R

    Your sorting algoritm can be replaced by one line of code.

    sort(numbers.begin( ), numbers.end());

    The problem is that you are sorting the array throwing away original indexes, but you need them for the return value.

    I have done something similar to you but first from the original vector I generated a second vector of pair<int, int> that stores the value and its original position.

    Then I sorted the original vector.

    Then I implemented a while loop similar to your.

    NOTE: you create the vector solution with two elemetns at the beginning (two zeros). But when you find a solution you append and not replace the elements.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.