What is the best way to optimise this list traversing function? instead of doing nested for loops?-CodePudding

How do you optimise this function that traverses the same list with nested for loops to find if there are two items when summed up results in the target sum? This implementation works but I would ideally like to not do nested loops.

std::pair<int, int> getTargetSumIndices(std::vector &list, int targetSum)
{
    for(int i = 0; i < list.size(); i  )
    {
        for(int k = 0; k < list.size(); k  )
        {
            if(i != k) 
            {
                int sum = list[i]   list[k];
                if(sum == targetSum) return std::make_pair(i, k);
            }
        }
    }

    return std::make_pair(-1, -1);
}

void main() 
{
    std::vector<int> list = {0, 3, 5, 6, 6, 2, 8};
    std::pair<int, int> indices = getTargetSumIndices(list, 10);        
}

CodePudding user response：

If you want to do lots of queries, or the size of list is very big, creating a map for list is worth it. The code is as follows.

#include<iostream>
#include<vector>
#include<unordered_map>

std::pair<int, int> getTargetSumIndices(std::vector<int> &list, int targetSum)
{
    std::unordered_multimap<int, int> listmap;
    for (int i = 0; i < list.size();   i) {
        listmap.insert(std::pair<int,int>(list[i], i));
    }
    for (int i = 0; i < list.size();   i) {
        auto its = listmap.equal_range(targetSum - list[i]);
        for (auto itor = its.first; itor != its.second;   itor) {
            if (i != itor->second) {
                return std::make_pair(i, itor->second);
            }
        }
    }

    return std::make_pair(-1, -1);
}

void main()
{
    std::vector<int> list = { 0, 3, 5, 6, 6, 2, 8 };
    std::pair<int, int> indices = getTargetSumIndices(list, 10);
}

I notice that variable 'list' contains some repeated elements, so I use multimap here. However, if your data size is not very bog, or you don't do queries frequently, the nested loops is much better, since the construction of hash map also costs time. Besides, the code you provide can also be improved, you can change the nested loop, and get rid of if(i!=k). Like this:

for(int k=i 1;k<list.size();  k)

CodePudding user response：

Base on the comments posted by @Phil1970 and @doug I performed a sort and then improved the recursion to achieve this.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

std::pair<int, int> getTargetSumIndices(std::vector<int> &list, int targetSum)
{
    std::sort(list.begin(), list.begin()   list.size());
    int start = 0;
    int end = list.size() - 1;
    
    while(start < end)
    {
        if (list[start]   list[end] == targetSum) 
        {   
            return std::make_pair(start, end); 
        }
        else if (list[start]   list[end] < targetSum) 
            start  ; 
        else 
            end--; 
    }

    return std::make_pair(-1, -1);
}

int main() 
{
    std::vector<int> list = {0, 3, 5, 6, 6, 2, 8};
    std::pair<int, int> indices = getTargetSumIndices(list, 10);
    
    std::cout << indices.first << ", " << indices.second << "\n";
    return 0;
}