查找与条件阵列对

Question

让说，我有一个int数组，我想找到一个对数的本阵，这对的总和等于一个数，像这样：

func findPair(list: [Int], _ sum: Int) -> (Int, Int)? { 
    for i in 0..<list.count - 1{ 
     for j in (i+1)..<list.count { 
      let sumOfPair = list[i] + list[j] 
      if sumOfPair == sum { 
       return (list[i], list[j]) 
      } 
     } 
    } 
    return nil 
} 

第一个参数是一个Int数组，第二个参数是我们需要比较该数组中某些对的数字。

例如：

findPair([1,2,3,4,5], 7) // will return (2, 5), because 2 + 5 = 7 

但是该算法的复杂度为为O（n^2）。

有没有更快的方法？

Answer 1

试试这个：

func findPair(list: [Int], _ sum: Int) -> (Int, Int)? { 
    //save list of value of sum - item. 
    var hash = Set<Int>() 
    var dictCount = [Int: Int]() 
    for item in list { 

     //keep track of count of each element to avoid problem: [2, 3, 5], 10 -> result = (5,5) 
     if (!dictCount.keys.contains(item)) { 
      dictCount[item] = 1 
     } else { 
      dictCount[item] = dictCount[item]! + 1 
     } 
     //if my hash does not contain the (sum - item) value -> insert to hash. 
     if !hash.contains(sum-item) { 
      hash.insert(sum-item) 
     } 

     //check if current item is the same as another hash value or not, if yes, return the tuple. 
     if hash.contains(item) && 
      (dictCount[item] > 1 || sum != item*2) // check if we have 5+5 = 10 or not. 
     { 
      return (item, sum-item) 
     } 
    } 
    return nil 
} 

Answer 2

试试下面的办法：

sort(arr,arr+n);//Sort the array 

low=0; 

high=n-1; // The final index number (pointing to the greatest number) 

while(low<=high) 
{ 
    if(arr[low]+arr[high]==num) 
    {  print(low,high); 
      break; 
    } 
    else if(arr[low]+arr[high]<num) 
     low++; 
    else if(arr[low]+arr[high]>num) 
     high--; 

} 

基本上，你在下面在这里贪婪的方法...希望工程.. :)

Answer 3

有一定的速度要快得多为O（n）来解决这个问题。下面是针对伪算法： -

1) Sort the given array. 
2) Take two pointers. One pointing to the beginning and other pointing to the end. 
3) Check if sum of two values pointed by two pointer is equal to given number. 
4) If yes then return. 
5) If greater than increment first pointer and go to step 3. 
6) Else increment second pointer and go to step 3.*