1

So I'm trying to solve problem of finding two numbers from an array such that they add up to a specific target number. The simplest way to solve it (it gives TimeLimit Error, because it takes O(n^2) time)

vector<int> res, temp = numbers;
sort(temp.begin(), temp.end());
for (int i = 0; i < numbers.size(); i++)
{
    for (int j = i + 1; j < numbers.size(); j++)
    {
        if (numbers[i] + numbers[j] == target)
        {
            res.push_back(i + 1);
            res.push_back(j + 1);
            return res;
        }
    }
}

Also I've tried to sort array before find and then use two pointers (Now it takes O(n^2 log n) time but still gives me Time Limit Error)

vector<int> twoSum(vector<int> &numbers, int target) {
    vector<int> res, temp = numbers;
    sort(temp.begin(), temp.end());
    int i = 0, j = numbers.size() - 1;
    while (i < j)
    {
        if (temp[i] + temp[j] == target)
        {
            res.push_back(i);
            res.push_back(j);
            break;
        }
        if (temp[i] + temp[j] < target)
            i++;
        if (temp[i] + temp[j] > target)
            j--;
    }
    for (int i = 0; i < numbers.size(); i++)
    {
        if (numbers[i] == temp[res[0]])
        {
            res[0] = i + 1;
            break;
        }
    }
    for (int i = 0; i < numbers.size(); i++)
    {
        if (numbers[i] == temp[res[1]])
        {
            res[1] = i + 1;
            break;
        }
    }
    return res;
}

So I would like to know how it is possible to solve this problem using only O(n) time? I've heard somthing about hash and map but don't know what are they and how to use them.

yizzlez
  • 8,639
  • 4
  • 28
  • 44
York's
  • 164
  • 10

1 Answers1

2

The hash table approach is as follows: (using unordered_set in C++11)

  • Given a target sum S...

  • For each element x:

    • Check if S - x exists in the hash table - if so, we have our 2 numbers x and S - x.

    • Insert x into the hash table.

This runs in expected O(n) time.

Also, your approach is only O(n log n). That's O(n log n) for the sort and O(n) for each of the while loop and the two for loops, giving O(n log n + n) = O(n log n) in total. Well, that's assuming .size() is O(1) - I know it might be O(n) (giving O(n²) total running time), at least for older compilers.

Although I'm not too sure what the last two for loops are doing there - when you break from the while loop, you'll have your 2 numbers.

Bernhard Barker
  • 52,963
  • 14
  • 96
  • 130