Number of values in a vector that add up to a sum S

I have the following task:

Write the function that has the header:long long CountSumS(vector<int> &a, int s)

The function will return the number of pairs with (a[i], a[j]); i < j; a[i] + a[j] = s)
Example:
If a = (8, 2, 3, 8, 7, 5) and s = 10, the function will return 3, the pairs being (8, 2), (2, 8) and (3, 7)

I'm also trying to do this efficiently, so simply taking every other element and checking the sum of all the values after it isn't the solution I'm looking for.

I tried solving this using an unordered multimap and I have the following function:

long long CountSumS(vector<int>& v, int sum)
{
    int cnt = 0;
    typedef unordered_multimap<int, int>::iterator iter;
    unordered_multimap<int, int> m;

    for (int i = 0; i < v.size(); i++)
        m.insert(make_pair(v[i], i));

    for (int i = 0; i < v.size(); i++)
    {
        int x = sum - v[i];
        //the needed value to make the sum

        pair<iter, iter> result = m.equal_range(x);
        int count = distance(result.first, result.second);

        if (count != 0)
        {
            for (auto iter = result.first; iter != result.second; iter ++) //iterates through the values 
            {
                if (iter->second > i)
                    cnt++;
                /*else
                    iter = m.erase(iter);*/
            }
        }
    }
    return cnt;

It solves the problem inefficiently because after all it just checks through all elements with a certain key, so the solution I thought of was to delete all elements in the map that have value smaller than "i", since it means the element has already been passed in the vector and I can't use it to form a sum anyway. The section written in the /**/ was my approach at trying to erase the value at that iterator, but I get an error when I tried to run the code (image)(https://i.stack.imgur.com/Nl3SI.png). I was wondering what was causing that error.

I appreciate all input on a better aproach for an easier solution, it was just the first thing I could think of and tried to implement.

Using iter ++ after iter = m.erase(iter) may result in an iterator overrun.

Do only one of them in each iteration.

            for (auto iter = result.first; iter != result.second; ) //iterates through the values 
            {
                if (iter->second > i)
                {
                    cnt++;
                    iter++;
                }
                else
                    iter = m.erase(iter);
            }

If you want only to return the number of pairs with (a[i], a[j]); i < j; a[i] + a[j] = s, you could use a different approach.

Instead of creating a std::unordered_multimap<int,int> container, that is a hash table, and insert all the pairs of the elements into it before checking the pairs that satisfy your predicate, you should use another std::vector<int> container, which elements are sorted. Thus, if you have an element a[i] and you need to find some other element a[j], with i < j, that satisfy the equivalence a[i] + a[j] = s, you will iterate through the container in the range.

About the efficiency, I can advice you to do the following optimizations: transfer the elements from the given vector to your vector using a copy ctor, so you avoid future reallocations and your code is clearer; sort the vector using a standard algorithm, i.e. std::sort().

So, you can take advantage of a binary search algorithm to find the number of elements for each element a[i] therefore the sum will not exceed the given range.

The algorithm is the following.
Initialize variables say, right as a.size() – 1 and count as 0 to store numbers of pairs whose sum lies over the range [L, U]. Iterate until the right is greater than 0, and find the starting index of the element whose sum with a[right] is greater than or equal to L. Then, find the ending index of the element before a[right] whose sum with a[right] is less than or equal to U. If the end is greater than equal to the start, then add (end – start + 1) to the count representing the number of elements whose sum with the current element lies over the range [L, U] and then decrement right.

Furthermore, you should correct a little, but not important, error: the function argument std::vector<int>& should be a constant reference const std::vector<int>&, since the elements it contains are never modified.