Сумма двух чисел, равных заданному числу

Question

У меня есть массив с положительными целыми числами в случайном порядке. A число x из списка дано, нам нужно найти любые два числа в списке , имеющем сумму, равную x. Время воспроизведения должно быть меньше n^2.

{править} То, что я сделал то, что я ставлю все цифры меньше, чем половина х в одном массиве и более чем в половине х в другом массиве, и все больше х отбрасываются, а затем идея что требуемые два числа должны быть из двух массивов (не из одного массива), и путем итерации я могу получить два числа.

Теперь для наихудшего случая я немного путаюсь в том, что подход хорош? или если кто-нибудь поможет мне что-то более лучшее, чем это, мы также сможем достичь log n или n * log n?

Answer 1

Ваше решение неверно, и в O(n^2).

1. Это неправильно, так как считают x=5 и arr=[1,2,3,5] - два числа, необходимые являются из одного массива, а не от обоих.
   Что делать, если arr=[3,3,6], x=6, вы поместите оба 3 с в одном списке (не больше, чем x/2, например), и не сможет найти 3+3=6.
2. Ваш алгоритм работает в O(n^2), так как предполагается, что половина элементов больше x , а половина меньше x. Тогда число комбинаций вы должны проверить, являются (n/2*n/2) /2 = n^2/8

---

Чтобы решить эту проблему в O(nlogn), подумайте, что произойдет, если вы сортировать данные, учитывая ряд arr[i], вы можете найти эффективно, если существует такое число x-arr[i] в отсортированном сейчас массиве?

Вы можете даже улучшить выше для O(n) среднего случая путем размещения элементов в хэш-набор, и теперь, учитывая номер y, вы можете найти эффективно, если x-y также в наборе?

EDIT:
Stroked из части не имеют значения больше, так как OP Editted вопрос, добавил новую причину беспокойства вместо этого.

---

(1) than x/2 в измененном вопросе.

Answer 2

Здесь вы идете,

Сортировка массива с помощью сортировка слиянием (Временная сложность: n logn). Возьмите два указателя/счетчика, скажем i & j, один начинается с индекса 0, а другой от n-1 (при условии, что n размер массива равен n).

if array[i]+array[j]=sum 
     return; 
    else if (array[i]+array[j]<sum) i++; 
    else j--; 

Сделайте это до i>j.

Общая Трудоемкость: п LOGN

Answer 3

общественного недействительными функции (INT [] массив, Int сумма) {

 for(int i = 0; i < array.length/2; i ++){ 
     for(int j = array.length-1;; j--){ 
      if(array[i]+array[j] < sum) break; 
      if(array[i]+array[j] == sum) System.out.println(array[i]+" + "+array[j]+" = "+sum); 
     } 
    } 
} 

Answer 4

операции

/* Время Сложность = O (п) -since Hashmap принять O (1) время */

public static ArrayList<Integer> twoSum(int[] arr , int target){ 

    if (arr == null){ 
     throw new IllegalArgumentException(); 
    } 
    ArrayList<Integer> targetHolder = new ArrayList<>(); 
    HashMap<Integer, Integer> map = new HashMap<>(); 

    for (int i = 0 ; i < arr.length ; i++){ 

     if (map.containsKey(arr[i])){ 
      int index = map.get(arr[i]); 
      targetHolder.add(index+1); 
      targetHolder.add(i+1);    
     } 
     else{ 
      map.put(target-arr[i], i);    
     } 

    } 
    return targetHolder;  
} 
public static void main(String[] args) {   
    int[] A = {1,2,3,4,5,6}; 
    System.out.println(twoSum(A, 6)); 
} 
} 

Answer 5

Здесь о (п) решение для нахождения первой пары индексов массива, который подводит к ожидаемой цели. Решение остановится, когда он найдет первые 2 индекса, которые суммируют для цели, если вам нужны все пары, которые добавляют к цели, вместо того, чтобы использовать результат int [], вы можете использовать ArrayList или даже карту, обрабатывать полный массив и верните его со всеми парами индексов. Существует очевидное предположение, что функция hashcode карты действительно хороша, и не так много коллизий, чтобы операции карты выполнялись в O (1) раз.

import java.util.*; 

public class Solution { 

    public static void main(String[] args) { 
     int[] array = new int[] {1,2,4,7,12,67,12,5,9,1,10}; 
     System.out.println(Arrays.toString(sum(array, 68))); 
    } 

    public static int[] sum(int[] array, int target) { 
     int[] result = new int[2]; 
     Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
     // n iterations 
     for (int index = 0; index < array.length; index++) { 
      // constant 
      if (map.containsKey(target - array[index])) { 
       result[1] = index; 
       // constant 
       result[0] = map.get(target - array[index]); 
       return result; 
      } 
      // constant 
      map.put(array[index], index); 
     } 
     return result; 
    } 
}