Какой самый быстрый способ определить, соответствуют ли три числа в массиве указанному значению c? - PullRequest
Новая
       16

Какой самый быстрый способ определить, соответствуют ли три числа в массиве указанному значению c?

0 голосов
/ 25 апреля 2020

Число будет использоваться только 2 или 3 раза, если оно появится

Мне нужен алгоритм, чтобы пройти несколько модульных тестов.

Оба эти решения хеширования и сортировки не работают с большим массивом длительность теста.

Хеширование: 

 public bool SumOfThree(int[] values, int sum, out int v1, out int v2, out int v3)
        {
            v1 = 0;
            v2 = 0;
            v3 = 0;

            for (int i = 0; i < values.Length - 2; i++)
            {
                HashSet<int> s = new HashSet<int>();
                int curr_sum = sum - values[i];

                for (int j = i + 1; j < values.Length; j++)
                {
                    if (s.Contains(curr_sum - values[j]))
                    {
                        v1 = values[i];
                        v2 = curr_sum - values[j];
                        v3 = values[j];
                        return true;
                    }
                    s.Add(values[j]);
                }
            }
            return false;
        }

Сортировка: 

 public bool SumOfThree(int[] values, int sum, out int v1, out int v2, out int v3)
        {
            v1 = 0;
            v2 = 0;
            v3 = 0;
            Array.Sort(values);

            for (int i = 0; i < values.Length - 1; i++)
            {
                int l = i + 1;
                int r = values.Length - 1;
                int x = values[i];
                while (l < r)
                {
                    if (x + values[l] + values[r] == sum)
                    {
                        v1 = x;
                        v2 = values[l];
                        v3 = values[r];
                        return true;
                    }

                    else if (x + values[l] + values[r] < sum) l++;

                    else r--;
                }
            }
            return false;
}

Если вы обнаружите что-то не так с этими двумя решениями (с точки зрения производительности) или узнаете что-нибудь быстрее я был бы признателен.

Я также читал кое-что об использовании бинарного поиска в отсортированном массиве, но не реализовал его успешно.

Большой массив выглядит следующим образом (необходимая сумма будучи 5 + 6 + 7 = 18) 

                List<int> list = new List<int>();
                for (int i = -600000; i <= -500000; ++i)
                {
                    list.Add(i);
                }
                for (int i = 100000; i <= 200000; ++i)
                {
                    list.Add(i);
                }
                list.Add(5);
                list.Add(6);
                list.Add(7);
                Randomize<int>(list);
                array = list.ToArray();
...