0

I'm doing a leetcode challange where I'm given a vector of integers and a target sum. My goal is to find and return a vector containing indices of the pair of indexes which point to values that when summed is equal to some target value.

This is my current solution:

#include <algorithm>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        auto bitr = nums.begin();
        auto eitr = nums.end()-1;
        sort(bitr, eitr);
        vector<int> output;

        while(bitr != eitr)
        {
            if(*bitr + *eitr == target)
            {
                output.push_back(distance(nums.begin(),bitr));
                output.push_back(distance(nums.begin(),eitr));
                break;
            }
            else if(*bitr + *eitr > target)
                eitr--;
            else if(*bitr + *eitr < target)
                bitr++;
        }
        return output;
    }
};

It passes 6/33 test case, but fails cases such as:

Input: [3,2,4] 6 Output: [0,2] Expected: [1,2]

Rhathin
  • 1,176
  • 2
  • 14
  • 20
Vocaloidas
  • 360
  • 2
  • 17
  • 1
    You have sorted the vector, so the iterators are not guaranteed to represent the same index as they used to in the original vector. – ph3rin Dec 30 '19 at 01:36
  • Hi, I changed to sort(nums.begin(), nums.end()); auto bitr = nums.begin(); auto eitr = nums.end()-1; But it's still the same. – Vocaloidas Dec 30 '19 at 01:38
  • 3
    @Vocaloidas The problem is that `sort` sorts the array and you then return the indices for this new array. After the `sort` you don't know anymore which index each element had before the sorting. See [this question](https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes) for how to keep track of the indices, so you can map them back later. – walnut Dec 30 '19 at 01:43
  • @Vocaloidas -- There is no need to sort values. The usual way to solve this problem is to use a hash set. – PaulMcKenzie Dec 30 '19 at 01:48

0 Answers0