returning vector indices

[DonnaPin]

Hello, I am trying a leetcode problem basically for the first time (tried a few weeks ago and didnt know vectors so didnt get very far). I have just went over vectors the past few days and now doing a problem which uses one. Im sure the way I am doing this problem is not the best way, but it is what I came up with but I can not seem to get it to return the indices needed.

The problem is

"Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice."

The code I have came up with so far is below. I think i just need to give back the two indices the it and it2 point to but I can not figure a way to do that. Is it even possible? I have marked with ****** where I believe i need to return the two indices. I was assuming something along the lines of return it, it2; but believe there is a conversion error with this.

  class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int>::iterator it;
        vector<int>::iterator it2;
        
        for(it = nums.begin(); it < nums.end(); it++)
        {        
            for(it2 = it + 1; it2 < nums.end(); it2++)
            {
                if(*it + *it2 == target)
                cout << *it << *it2;   
                return **********
                   
            }         
        }
        
               
    }
};

[jonnin]

you don't need a class in c++ to do a function, if you did not know.
there isnt anything wrong with it either.

n*n approach is usually a loser with these kinds of problems ... the point is to find some better way and they often throw you a couple million so that your answer will take too long.

dunno that its the 'best' but the 'obvious' improvement, with nothing clever, might go like this:

1) build your array as an array of structs of 2 integers (or at tuple if you know that or want to learn about it). one item will be the array index, so the [0] array location would have say (0, 1003) and the [1] location would have (1, 42) or whatever the numbers really are.
2) sort the array by the values (not the index values, you already have that!)
3) make an array of target - array value for each array data value.
4) search for the each value from #3 in the array made by sorting in #2 using binary search.
when you find it, the found value has its index on it, and the #3 array is in order so you know what index that piece had too, so you have both indices.
etc
that is NlgN instead of N*N, and the NlgN is from the sort. If you can counting sort instead or use any other integer exploits, it would be N instead of NlgN, which would really be quick.

[adam2016]

As Jonnin already mentioned you want to return a pair of numbers in this case the indices of the 2 numbers that sum to the target number.

I mean you could technically return a vector<int>(your return type) and populate it with just the two indices but that seems a tad bit overkill.

Iterate through the numbers until you hit the target number, your approach is correct you will need a nested loop.

also don't forget to return something in the case none of the numbers meet your target.

[DonnaPin]

Hi, I am still reading through the responses but just wanted to add that the site gave starter code, ie the class and vector return type. The full code that they supplied is below

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
};

Thank you for replies so far.

[dutch]

They probably expect you to use indices and not iterators.
It's easy to return two ints in a vector<int>:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < int(nums.size()) - 1; ++i)
            for (int j = i + 1; j < int(nums.size()); ++j)
                if (nums[i] + nums[j] == target)
                    return {i, j};
        return {-1, -1}; // not found
    }
};

[DonnaPin]

Thank you all for the replies. A lot of what Jonnin said I have not covered yet, such as tuples and binary search, but hopefully soon. And I see now that the solution dutch gave would have been a lot easier. I thought for once I had finally solved a problem almost to completion myself, but i guess not. My problem solving skills still are terrible xD.


EDIT:

Just while here I was wondering if someone could clarify something on vectors, and this problem, while doing it the way i was trying. The site says my output is [2] but im not understanding why this would be. I could understand if i was dereferencing it, but im not. Is it because im trying to return 2 iterator values?

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int>::iterator it;
        vector<int>::iterator it2;
        
        for(it = nums.begin(); it < nums.end(); it++)
        {        
            for(it2 = it + 1; it2 < nums.end(); it2++)
            {
                if(*it + *it2 == target)
                {
                    cout << "Matched " <<  *it  << " "<< *it2;                       
                    return {it, it2};                    
                }   
                else
                {
                    cout << "not matched";
                }
              
             } 
            
                
        }
        
             return {-1,-1};
    }
};

site says output is (it is the output [2] that i am confused with)

our input
[2,7,11,15]
9

stdout
Matched 2 7

Output
[2]

Expected
[0,1]

[keskiverto]

Yes, iterators are not integers.
How that compiles and what implicit conversions it does ... I don't want to think about.

dutch shows that you can iterate vector with indices.

There is a way to calculate index from iterator. See http://www.cplusplus.com/reference/iterator/distance/

int first_index = std::distance( nums.begin(), it );
int other_index = std::distance( nums.begin(), it2 );

It is also said that "if iterator is a random-access iterator, the function uses operator- to calculate this."

Does vector have random-access iterators?
If it does, then

int first_index = it - nums.begin();
int other_index = it2 - nums.begin();

[seeplus]

Does vector have random-access iterators?

Yes.

Why return a vector of just 2 values? Why not a pair? Why return indexes and not iterators?

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

using namespace std;

auto twoSum(const vector<int>& nums, int target)
{
	for (auto it = nums.begin(); it != nums.end(); ++it)
		for (auto it2 = it + 1; it2 != nums.end(); ++it2)
			if (*it + *it2 == target) {
				cout << "Matched " << *it << " " << *it2;
				return pair{it, it2};
			}

	cout << "not matched";
	return pair{nums.end(), nums.end()};
}

[keskiverto]

Why return a vector of just 2 values? Why not a pair? Why return indexes and not iterators?

I bet the teachers belong to the "one step at a time" school and that this "vector-step" does not contain iterators.

[Ganado]

Which, in my opinion, is fine for a beginner. DonnaPin's prompt does not mention iterators, so you might as well just use a classic i/j nested for loop and not deal with std::distance or iterator-index conversions.

[seeplus]

I only asked about returning iterators as @DonnaPin's code above uses iterators.

[keskiverto]

I do agree with Ganado.

DonnaPin wrote:

(tried a few weeks ago and didnt know vectors so didnt get very far). I have just went over vectors the past few days and now doing a problem which uses one. Im sure the way I am doing this problem is not the best way, but it is what I came up with but I can not seem to get it to return the indices needed.

DonnaPin shows initiative, which is good in itself. However, at this point it is important to notice that vector can be iterated with index, just like plain array, and that that is more appropriate than the iterator-based approach for this problem.

[DonnaPin]

Hi, thanks again for all the replies. Some of the stuff I have not covered yet such as a pair suggested by seeplus, so I will look into these things.

I think I really need to go over vectors a lot more in detail, an especially iterators. I think this problem has shown me that (even though for this solution I really didnt need them xD).