returning vector indices

Nov 18, 2020 at 8:57pm
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  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 **********
                   
            }         
        }
        
               
    }
};
Nov 18, 2020 at 11:17pm
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.
Nov 18, 2020 at 11:41pm

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.

Nov 18, 2020 at 11:52pm
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

1
2
3
4
5
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
};


Thank you for replies so far.
Nov 19, 2020 at 3:18am
They probably expect you to use indices and not iterators.
It's easy to return two ints in a vector<int>:

1
2
3
4
5
6
7
8
9
10
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
    }
};

Nov 19, 2020 at 1:20pm
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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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]
Last edited on Nov 19, 2020 at 2:00pm
Nov 19, 2020 at 2:59pm
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/
1
2
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
1
2
int first_index = it - nums.begin();
int other_index = it2 - nums.begin();

Last edited on Nov 19, 2020 at 3:02pm
Nov 19, 2020 at 5:02pm
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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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()};
}

Last edited on Nov 19, 2020 at 5:21pm
Nov 19, 2020 at 6:10pm
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.
Nov 19, 2020 at 6:18pm
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.
Nov 19, 2020 at 6:22pm
I only asked about returning iterators as @DonnaPin's code above uses iterators.
Nov 19, 2020 at 8:16pm
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.
Nov 19, 2020 at 9:04pm
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).
Topic archived. No new replies allowed.