Вычислять пары из массива, сумма которого равна заданному числу?

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

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 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; } 

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

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

 public static int numberOfPairs(Integer[] array, int sum) { Set set = new HashSet<>(Arrays.asList(array)); // this set will keep track of the unique pairs. Set uniquePairs = new HashSet(); 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(); } 

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

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

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

 public static int numberOfPairs(int[] a, int k ){ int count=0; List 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 , но это оптимизация.