Лучший способ найти все значения двух переменных, имеющих определенную сумму

Question

У меня есть две переменные i, j, неизвестные во время выполнения. У меня есть два предела maximumi и maximumj, значения которых известны так, что i находится между 0 и его соответствующим пределом (одинаковым для j). У меня есть другая переменная, которая известна во время выполнения и представляет собой сумму i и j. Мне нужно найти все значения i и j, которые имеют сумму, равную переменной sum, перед выполнением определенного вычисления с использованием i и j. То, что я пробовал, - это использовать один вложенный цикл и просто грубо заставить найти значения i и j, так что для каждого возможного я добавляю все возможные j и проверяю, равна ли сумма сумме. Это отлично работает для небольших пределов, но поскольку мои ограничения приближаются к бесконечности, алгоритм растет ужасно. У меня есть порог в 3 секунды, чтобы найти эти цифры. Есть ли рекомендуемая структура данных для моей ситуации.

Answer 1

var sum = 99999999; 
var max = 60000000; 
var min = 10000000; 

var i = max; 
var j = sum - max; 

var result = new List<Tuple<int, int>>(); 
while (j >= min && j =< max) 
{ 
    result.Add(new Tuple<int, int>(i, j)); 
    i--; 
    j++; 
} 

Нет необходимости BruteForce, поскольку это может быть легко вычисляется. Работает ровно в течение нескольких миллисекунд, даже с большими промежутками между макс и мин.

Answer 2

Вам нужен только один цикл (например i от 0 к sum) и j будет всегда равна sum - i. Нет необходимости создавать вложенный цикл для j, так как его значение всегда известно.

int sum = 1337; 
for (int i = 0; i <= sum; i++) 
{ 
    var j = sum - i; 
    Console.WriteLine("{0} + {1} = {2}", i, j, sum); 
} 

Answer 3

Вы можете просто перечислить их?

List<Tuple<int, int>> options = new List<Tuple<int, int>(); 
for(int a=0; a < sum; a++) 
    options.Add(new Tuple<int, int>(a, sum-a)); 

Отрегулируйте ваши границы, конечно.

Answer 4

int min(int a, int b){ return a < b ? a : b; } 
int max(int a, int b){ return a > b ? a : b; } 

void pairs(int sum, int maxi, int maxj){ 
    if(maxi + maxj < sum) return; 
    maxi = min(maxi, sum); 
    maxj = min(maxj, sum); 
    for(int i = max(0, sum - maxj); i <= min(maxi, sum); i++){ 
    std::cout << "i=" << i << ", j=" << (sum - i) << std::endl; 
    } 
}