Поиск суммы в массиве

Question

У меня есть метод, который подсчитывает, сколько сумм из 3 элементов, равных 0, содержит массив. Мне нужна помощь в поиске пути , чтобы прекратить считать те же триплеты в цикле. Так, например, 1 + 3 - 4 = 0, но и 3 - 4 + 1 = 0.Here является метод:

private static int counter(int A[]) 
    { 
     int sum; 
     int e = A.length; 
     int count = 0; 
     for (int i=0; i<e; i++) 
     { 
      for (int j=i+1; j<e; j++) 
      { 
       sum=A[i]+A[j]; 
       if(binarySearch(A,sum)) 
       { 
         count++; 
       } 
      } 
     } 
     return count; 

редактировать: Я должен использовать двоичный поиск (массив сортируется). Вот код BinarySearch:

private static boolean binarySearch(int A[],int y) 
    { 
     y=-y; 
     int max = A.length-1; 
     int min = 0; 
     int mid; 
     while (max>=min) 
     {  
      mid = (max+min)/2; 
      if (y==A[mid]) 
      { 
       return true; 
      } 
      if (y<A[mid]) 
      { 
       max=mid-1; 
      } 
      else 
      { 
       min=mid+1; 
      } 
     } 
     return false; 

Answer 1

Вы можете избежать подсчета различных триплетов, сделав одно предположение, что нам нужно искать троек (х, у, г) с x < y < z и A[x] + A[y] + A[z] == 0.

Так что вам нужно сделать, это изменить функцию BinarySearch вернуть число индекса, который больше, чем у и имеет [г] == - (А [х] + A [у])

private static int binarySearch(int A[],int y, int index) 
    { 
     y=-y; 
     int max = A.length-1; 
     int min = index + 1; 
     int mid; 
     int start = A.length; 
     int end = 0; 
     while (max>=min) 
     {  
      mid = (max+min)/2; 
      if (y==A[mid]) 
      { 
       start = Math.min(start, mid); 
       max = mid - 1; 
      } else 
      if (y<A[mid]) 
      { 
       max=mid-1; 
      } 
      else 
      { 
       min=mid+1; 
      } 
     } 
     int max = A.length - 1; 
     int min = index + 1; 
     while (max>=min) 
     {  
      mid = (max+min)/2; 
      if (y==A[mid]) 
      { 
       end = Math.max(end, mid); 
       min= mid + 1; 
      } else if (y<A[mid]) 
      { 
       max=mid-1; 
      } 
      else 
      { 
       min=mid+1; 
      } 
     } 
     if(start <= end) 
      return end - start + 1; 
     return 0; 
} 

Таким образом, новая функция binarySearch вернет общее число индексов, превышающее index, и имеет значение равное y.

Так остальная часть работы заключается в подсчете ответа

private static int counter(int A[]) 
{ 
    int sum; 
    int e = A.length; 
    int count = 0; 
    for (int i=0; i<e; i++) 
    { 
     for (int j=i+1; j<e; j++) 
     { 
      sum=A[i]+A[j]; 
      count += binarySearch(A,sum, j); 

     } 
    } 
    return count; 
} 

Обратите внимание, как я использовал два бинарного поиска, чтобы найти начальный и конечный индекс всех значений больше, чем y!

Answer 2

private static int counter(int A[]) { 
    int e = A.length; 
    int count = 0; 
    for (int i = 0; i < e; i++) { 
     for (int j = 1; (j < e - 1) && (i != j); j++) { 
      for (int k = 2; (k < e - 2) && (j != k); k++) { 
       if (A[i] + A[j] + A[k] == 0) { 
        count++; 
       } 
      } 
     } 
    } 
    return count; 
} 

Answer 3

private static int counter(int ints[]) { 
    int count = 0; 
    for (int i = 0; i < ints.length; i++) { 
    for (int j = 0; j < ints.length; j++) { 
     if (i == j) { 
     // cannot sum with itself. 
     continue; 
     } 
     for (int k = 0; k < ints.length; k++) { 
     if (k == j) { 
      // cannot sum with itself. 
      continue; 
     } 

     if ((ints[i] + ints[j] + ints[k]) == 0) { 
      count++; 
     } 
     } 
    } 
    } 

    return count; 
} 

Answer 4

Чтобы решить проблему с бинарным поиском
Ваш код был почти правильно. все, что вам нужно сделать, это просто заменить

if (sum == binarySearch(A,sum)) { 

с этим

if (binarySearch(A,sum)) { 

Я предполагаю, что ваш метод binarySearch(A, sum) возвратит true, если он будет найден sum в A массиве еще false

Answer 5

Вот мое решение, предполагающее, что массив отсортирован и нет повторяющихся элементов, я использовал функцию двоичного поиска, которую вы предоставили. Может ли входной массив содержать повторяющиеся элементы? Не могли бы вы предоставить некоторые тестовые примеры?

Чтобы не считать одни и те же триплеты в цикле, мы должны иметь способ проверки повторяющихся элементов, основная идея, которую я использовал здесь, - это иметь список массивов int [], сохраняющих отсортированные целые числа {A[i],A[j],-sum}. Затем на каждой итерации я сравниваю новые A [i] и A [j] с записями в списке, тем самым устраняя повторяющиеся.

private static int counter(int A[]){ 
    int sum; 
    int e = A.length; 
    int count = 0; 
    List<int[]> elements = new ArrayList<>(); 
    boolean mark = false; 
    for (int i=0; i<e; i++) 
    { 
     for (int j=i+1; j<e; j++) 
     { 
      sum=A[i]+A[j]; 

      if (-sum == binarySearch(A,sum)){ 
       int[] sort = {A[i],A[j],-sum}; 
       if(-sum == A[i] || -sum == A[j]){ 
        continue; 
       }else{ 
        Arrays.sort(sort); 
        //System.out.println("sort" + sort[0] + " " + sort[1]+ " " + sort[2]); 
        for (int[] element : elements) { 
         if((element[0] == sort[0] && element[1] == sort[1]) && element[2] == sort[2]) 
          mark = true; 
        } 
        if(mark){ 
         mark = false; 
         continue; 
        }else{ 
         count++; 
         elements.add(sort); 
         //System.out.println("Else sort" + sort[0] + " " + sort[1]); 
        } 
       } 
      } 
     } 
    } 
    return count; 
} 

Answer 6

вы можете использовать вспомогательный массив, который хранит флаг, указывающий, используется ли этот элемент; Введите код:

private static int counter(int A[]) 
{ 
    int sum; 
    int e = A.length; 
    int count = 0; 
    // assisted flag array 
    List<Boolean> flagList = new ArrayList<Boolean>(e); 
    for (int k = 0; k < e; k++) { 
     flagList.add(k, false);// initialization 
    } 
    for (int i=0; i<e; i++) 
    { 
     for (int j=i+1; j<e; j++) 
     { 
      sum=A[i]+A[j]; 
      // if element used, no count 
      if(binarySearch(A,sum)&& !flagList.get(i)&& !flagList.get(j)) 
      { 
        count++; 
        flagList.set(i, true); 
        flagList.set(j, true); 
      } 
     } 
    } 
    return count;