Алгоритм 2-SUM с использованием отсортированного вектора

Я пытаюсь реализовать вариант алгоритма 2-SUM с использованием отсортированного вектора на С++. Задача состоит в том, чтобы прочитать файл, содержащий 10 ^ 6 целых чисел, и вычислить количество различных целых чисел (x и y), которые в сумме дают t, где t находится в интервале [-10000, 10000]. Я протестировал свой код на нескольких тестовых примерах, и, похоже, он работает, но я не получаю правильного ответа на задание по программированию. Это для курса Coursera Algorithms: Design and Analysis. Таким образом, за это задание не будет получено официальное признание. Буду признателен за любую помощь. Вы можете найти мой код ниже.

/*
 * TwoSums.cpp
 * Created on: 2013-08-05
 * 
 * Description: Implemented a variant of the 2-SUM algorithm for sums between -10000 and 10000.
 * The task was to compute the number of target values t in the interval [-10000,10000]
 * (inclusive) such that there are distinct numbers x,y in the input file (./HashInt.txt)
 * that satisfy x+y=t. The input file was taken from the Algorithms: Design and Analysis course
 * taught by Tim Roughgarden on Coursera.
 * 
 */

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <set>

#define LOWER -10000
#define HIGHER 10000

using namespace std;

const char* inputfile = "./HashInt.txt";

/*
 * Precondition: The inputfile is a file that contains integers, both 
 *               positive and negative. Each line contains an integer.
 * 
 * Postcondition: Every number in the file will be stored in vector V. 
 */

int ReadFile(vector<long>& V) {
    std::string line;
    std::ifstream infile;
    infile.open(inputfile);

    if(infile.fail())
    {
        cout << "Problem opening file.";
        return -1;
    }

    while (getline(infile, line)) {
        istringstream iss(line);
        long a;
        iss >> a;
        V.push_back(a);
    }

    return 0;
}

/*
 * Precondition: V is a sorted vector of integers
 * 
 * Postcondition: The number of target values (t) in the interval
 * [-10000,10000] will be displayed in stdout such that there
 * are distinct numbers x,y in the input file that satisfy x+y=t.
 */

void TwoSum (const vector<long>& V) {
    vector<long>::iterator x;
    vector<long>::iterator y;
    unsigned long count = 0;

    for (int i = LOWER; i <= HIGHER; ++i) {
        x = V.begin();
        y = V.end()-1;

        while (x != y) {
            long sum = *x + *y;
            if (sum == i) {
                count++;
                break;
            }

            else if(sum < i) {
                x+=1;
            }

            else {
                y-=1;
            }
        }
    }
    cout << "Count is: " << count << endl;
}

int main () {

    // Read integers, store in vector
    vector<long>V;
    if (ReadFile(V) < 0) return -1;

    // Erase duplicate numbers and sort vector
    set<long> s;
    unsigned long size = V.size();
    for( unsigned long i = 0; i < size; ++i ) s.insert( V[i] );
    V.assign(s.begin(),s.end() );

    // Implement 2-SUM algorithm for numbers between -10000 and 10000
    TwoSum(V);

    return 0;
}

person Bilal    schedule 06.08.2013    source источник
comment
Возможный дубликат алгоритма линейного времени для 2-SUM   -  person Leonid Volnitsky    schedule 06.08.2013
comment
Как это терпит неудачу и с каким вводом?   -  person Useless    schedule 06.08.2013


Ответы (2)


Эта программа не запрашивает у пользователя ввод для использования в качестве значения 't'. Итак, я предполагаю, что вам не нужно количество пар x-y, которые в сумме составляют определенное t. Ваша программа перебирает все возможные значения для 't' и смотрит, есть ли пара x-y, которая суммируется с этим, а затем переходит к следующему значению для 't'.

person Remco Boom    schedule 06.08.2013

Я считаю, что вам нужно отсортировать вектор данных, прежде чем перейти к циклу через LOWER to HIGHER. Потому что данные должны быть отсортированы, чтобы применить алгоритм, который вы реализовали с x и y как двумя итераторами в противоположных направлениях.

person shreyans800755    schedule 21.08.2015