寻找“a + b = c + d”解决方案的更好算法

Question

因此，让abcd是介于1000和9999之间的数字，a，b，c，d是数字。 所以找到数字，其中a + b = c + d。有一个解决方案与四个循环，但我需要三个循环的解决方案。

for (int a = 1; a <= 9; a++) 
{ 
    for (int b = 0; b <= 9; b++) 
    { 
     for (int c = 0; c <= 9; c++) 
     { 
      for (int d = 0; d <= 9; d++) 
      { 
       if ((a + b) == (c + d)) 
       { 
        Console.WriteLine(" " + a + " " + b + " " + c + " " + d); 
       } 
      } 
     } 
    } 
} 

Answer 1

前3个循环为a，b和c建立值。知道这一点和你的方程只需计算出为了使方程成立就需要做什么。然后检查为d计算的数字是否有效。

for (int a = 1; a <= 9; a++) 
{ 
    for (int b = 0; b <= 9; b++) 
    { 
     for (int c = 0; c <= 9; c++) 
     { 
      d = a + b - c; 
      if (d <= 9 && d >= 0) 
      { 
      Console.WriteLine(" " + a + " " + b + " " + c + " " + d); 
      } 
     } 
    } 
    } 

Answer 2

如果有人问你解决x + 1 == 2方程，你居然试图遍历的x所有可能的值，看看哪个最适合？我希望不是。您可能会发现该公式允许立即直接分析解决方案x = 2 - 1 = 1。

相同的逻辑适用于您的案例。一旦知道a,b和c，您的a + b == c + d公式允许直接解决d：d = a + b - c。没有必要遍历d，就像无需遍历x的x + 1 == 2一样。

Answer 3

什么是4SUM的特例，可以通过其中一种方法来解决3SUM，使其成为O（N^2）。尽管它需要使用一些数据结构。

要注意的第一件事情是，因为你正在寻找A + B = C + d，你真的想要做的是找到数对，加起来一定数目的清单S.

你可以简单地通过使用一个map/dict来表示关键是总和，并将其映射到等于该总和的对的列表。其结果是：

S = [(a,b),(c,d),(e,f),...] for a number of values of S 

这相当于说：

a + b = c + d = e + f = ... = S for a number of values of S 

你那么只需经过各总和和删除的那些那里是只有在列表中的单个元素。

我想你可以打破通过组合获得像a + b = c + d和c + d = e + f之类的东西，但需要花费额外的O（N^2）作为只要没有重复，因为限制你有多少种方式可以获得一笔款项。虽然，我可能是错的，它需要O（N^3）列出解决方案的形式。

Answer 4

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace test 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      var number = Enumerable.Range(1000, 9000); 
      var list = from y in number 
         let a = y/1000 
         let b = (y - 1000 * a)/100 
         let c = (y - 1000 * a - 100 * b)/10 
         let d = (y - 1000 * a - 100 * b - 10 * c) 
         where a + b == c + d 
         select y; 
      foreach (var item in list) 
      { 
       Console.WriteLine(item); 
      } 
      Console.Read(); 
     } 
    } 
} 

Answer 5

String s1; 
Set<String> s=new TreeSet(); 
for(int i=1;i<10;i++) 
{ 
    s1=null; 
    s1=""+i; 
    for(int j=0;j<10;j++) 
    { 
     String tempj=s1; 
     s1=s1+j; 
     for(int k=0;k<10;k++) 
     { 
      String tempk=s1; 
     s1=s1+k; 
     int temp=i+j-k; 
     s1=s1+temp; 
     if(temp<10) 
     s.add(s1); 
     s1=tempk; 
     } 
     s1=tempj; 
    } 

} 

for(String i:s) 
System.out.println(i+); 

---------------------------------------- ------------------------编辑1 ------------------

import java.util.*; 
public class HelloWorld{ 

public static void main(String []args){ 
    String happyNumber; 
Set<String> numberSet=new TreeSet(); 
for(int i=1;i<10;i++) 
    { 
    happyNumber=null;   //Every 1st loop will give a new number so old one has to be deleted 
    happyNumber=""+i;   //Adding the number in 1st place (place value will be i*10000) 
    for(int j=0;j<10;j++)  //Loop for putting nmber in 1000th place 
     { 
      String tempj=happyNumber; //taking happyNumber(only one digit fixed till now) into a temp variable to permutate on other places 
      happyNumber=happyNumber+j; //Attaching another number after this we have (AB) 
      for(int k=0;k<10;k++)  //permutating with value of c and calculating d  
       { 
        String tempk=happyNumber; 
        happyNumber=happyNumber+k; //Attaching variable for 3rd place (c) 
        int temp=i+j-k;    //calculating value of d 
        if(temp<10)     //checking whether we have right value for d 
         { 
         happyNumber=happyNumber+temp; 
         numberSet.add(happyNumber); 
         } 
        happyNumber=tempk;   //bringing number back to its previous state for more combination 
       } 
       happyNumber=tempj;    //bringing number back to its previous state for more combination 
     } 

    } 

    for(String i:numberSet) 
    System.out.println(i); 
    } 
}