Число пар из массива, сумма которого равна заданному числу?

Question

У меня только что было онлайн-интервью по кодированию, и один из вопросов, заданных для данного массива целых чисел, узнать количество пар, суммирование которых равно определенному числу (переданному как параметр внутри метода). Например, массив задается как,

int[] a = {3, 2, 1, 45, 27, 6, 78, 9, 0}; 
int k = 9; // given number 

Таким образом, будет 2 пары (3, 6) и (9, 0), сумма которых равна 9. Это хорошо, чтобы отметить, что, как образуются пары не имеет значения. Средство (3,6) и (6,3) будет рассматриваться как одна и та же пара. Я представил следующее решение (на Java) и любопытно узнать, не пропустил ли я какие-либо проблемы с краем?

public static int numberOfPairs(int[] a, int k){ 

    int len = a.length; 

    if (len == 0){ 
     return -1; 
    } 

    Arrays.sort(a); 
    int count = 0, left = 0, right = len -1; 

    while(left < right){ 

     if (a[left] + a[right] == k ){ 

      count++; 

      if (a[left] == a[left+1] && left < len-1){ 
       left++; 
      } 

      if (a[right] == a[right-1] && right >1){ 
       right-- ; 
      } 

      right--; // right-- or left++, otherwise, will get struck in the while loop 
     } 

     else if (a[left] + a[right] < k){ 
      left++; 
     } 

     else { 
      right--; 
     } 
    } 

    return count; 
} 

Кроме того, может ли кто-нибудь предложить альтернативное решение проблемы? Благодарю.

Answer 1

Ваше решение является слишком сложным, вы можете сделать это упражнение намного более легким способом:

public static int numberOfPairs(int[] a, int k){ 

    int count=0; 
    List<Integer> dedup = new ArrayList<>(new HashSet<>(Arrays.asList(a))); 
    for (int x=0 ; x < dedup.size() ; x++){ 
     for (int y=x+1 ; y < dedup.size() ; y++){ 
      if (dedup.get(x)+dedup.get(y) == k) 
       count++; 
     } 
    } 

    return count; 
} 

Хитрость здесь иметь цикл, начиная после того, как индекс первой петли, чтобы не считать одни и те же значения в два раза, и не сравнить его с вашим собственным индексом. Кроме того, вы можете дедуплицировать массив, чтобы избежать дублирования пар, поскольку они не имеют значения.

Вы также можете отсортировать список, затем break цикл, как только ваша сумма идет выше k, но это оптимизация.

Answer 2

Пожалуйста, проверьте следующий код.

public static int numberOfPairs(Integer[] array, int sum) { 
    Set<Integer> set = new HashSet<>(Arrays.asList(array)); 

    // this set will keep track of the unique pairs. 
    Set<String> uniquePairs = new HashSet<String>(); 

    for (int i : array) { 
     int x = sum - i; 
     if (set.contains(x)) { 
      int[] y = new int[] { x, i }; 
      Arrays.sort(y); 
      uniquePairs.add(Arrays.toString(y)); 
     } 
    } 

    //System.out.println(uniquePairs.size()); 
    return uniquePairs.size(); 
} 

Сложность времени будет О (п).

Надеюсь, это поможет.