能否快速找出一個數組中的兩個數字,讓這兩個數字之和等於一個給定的值,為了簡化起見,我們假設這個數組中肯定存在至少一組符合要求的解。
法一:
最直接的方法就是,窮舉法,復雜度為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);