Найти сумма 3, что общая цель из списка


Связанной с Java вопрос у меня диковинки.

Все уникальные комбинации (не перемещаясь) 3 значений, сумма которых составляет цель из списка целых чисел.

Значения могут дублировать в списке, но используются только один раз.

Путем сортировки входных оценки способен принимать ярлыки.

Отзывы о код и скорость, пожалуйста.

Предположим, что все входные и сумма >= 0.

public static List<List<int>> FindThreeSum(List<int> input, int sum = 24)
{
    //cannot have default on a list to my knowledge
    if(input.Count < 3)
    {
        input = new List<int> { 8, 12, 6, 18, 4, 3, 8, 1, 6, 3, 8, 9, 0 };
        //in real life throw an error
    }
    List<int> sortedInput = input.OrderBy(x => x).ToList();
    Debug.WriteLine(string.Join(", ", sortedInput));
    int sortedCount = sortedInput.Count;
    int maxInput = sortedInput[sortedCount - 1];
    List<List<int>> findSum = new List<List<int>>();
    if (3 * (long)maxInput < (long)sum || sortedInput[0] < 0 || sum < 0 || 3 * sortedInput[0] > sum)
    {
        return findSum;
    }          
    int sumSoFar;
    int sumI = int.MaxValue;  
    int sumJ = 0;
    int sumK = 0;
    for (int i = 0; i < sortedCount - 2; i++)
    {
        if(sortedInput[i] == sumI)
        {
            continue; 
        }
        sumI = sortedInput[i];
        if(3 * sumI > sum)  
        {   
            break;  //sumSoFar is only going to get bigger
        }
        for (int j = i + 1; j < sortedCount - 1; j++)
        {
            if (sortedInput[j] == sumJ)
            {
                continue;
            }
            sumJ = sortedInput[j];
            sumSoFar = sumI + sumJ;
            if (sumSoFar + sumJ > sum)
            {
                break;
            }
            else if(sumSoFar + maxInput < sum)
            {
                continue;
            }
            for (int k = j + 1; k < sortedCount; k++)
            {
                if (sortedInput[k] == sumK)
                {
                    continue;
                }
                sumK = sortedInput[k];
                sumSoFar = sumI + sumJ + sumK;
                if (sumSoFar > sum)
                {
                    break;
                }
                else if(sumSoFar == sum)
                {
                    findSum.Add(new List<int> { sumI, sumJ, sumK });
                    Debug.WriteLine($"{sumI} {sumJ} {sumK}");
                }
            }
        }
    }
    Debug.WriteLine("daDone");
    return findSum;
}


165
2
задан 25 марта 2018 в 02:03 Источник Поделиться
Комментарии
1 ответ

В целом это выглядит ОК для меня, но вы могли бы рассмотреть следующие:

1) вернуть IEnumerable<int[]> вместо List<List<int>> и тогда дают положительные результаты, когда нашли:

            ...
else if (sumSoFar == sum)
{
yield return new int[] { iValue, jValue, kValue };
}...

2) имена суми sumJ, sumK несколько вводит в заблуждение, поскольку они не подводит. Лучше имена будут valueI, -Джей, -к

  int valueI;
int valueJ;
int valueK;

3) для удовольствия, вы могли бы рассмотреть: потому что вы в основном сделать то же самое же цикл вложен в три раза, он может стать кандидатом в рекурсивной функции перебора каждое слагаемое и получая все положительные суммы. Таким образом можно обобщить алгоритм для обработки любого количества слагаемых...

2
ответ дан 26 марта 2018 в 07:03 Источник Поделиться