編程之美 快速尋找滿足條件的兩個數

能否快速找出一個數組中的兩個數字，讓這兩個數字之和等於一個給定的值，為了簡化起見，我們假設這個數組中肯定存在至少一組符合要求的解。

        法一：

         最直接的方法就是，窮舉法，復雜度為O(N^2);

         法二：

         利用sum減去a[i],再查找sum-a[i]，是否在數組裡，這時候就變成查找了，可利用二分查找；排序的復雜度為O(nlgn)，查找的復雜度為O(lgn),最終的復雜度為O(nlgn)；

         ,也可以利用hash查找，只不過空間復雜度增加O(N);

         法三：先排好序，然後，i=0,j=n-1,看arr[i]+arr[j]是否等於sum,等於停止查找，小於sum，i++；大於sum，j--；復雜度為O(N)+O(NlgN);

for(i=0;j=n-1;i<j;) 
   if(arr[i]+arr[j]==sum) 
        return (i,j); 
   else if(arr[i]+arr[j]<sum) 
       i++; 
   else 
       j--; 
   return (i,j); 

for(i=0;j=n-1;i<j;)
   if(arr[i]+arr[j]==sum)
     return (i,j);
   else if(arr[i]+arr[j]<sum)
    i++;
   else
    j--;
   return (i,j);