? ?能否快速的在數組中找到兩個數，讓這兩個數之和等于一個給定的數字。

解法1、

一個直接的解法就是窮舉：從數組中任意取出兩個數字，計算兩者之和是否為
給定的數字。?
顯然其時間復雜度為N（n-1）/2即O（N^2）。這個算法很簡單，寫起來也很容
易，但是效率不高。一般在程序設計里面，要盡可能降低算法的時間和空間復雜度，
所以需要繼續尋找效率更高的解法。

vector<double> mindifference(double arr[], int n, int num) {vector<double>result;for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){if (arr[i] + arr[j] == num){result.push_back(arr[i]);result.push_back(arr[j]);break;}}}return result; }

解法二?
求兩個數字之和，假設給定的和為Sum。一個變通的思路，就是對數組中的每個
數字arr[i]都判別Sum-arr[i]是否在數組中，這樣，就變通成為一個查找的算法。

vector<double> mindifference(double arr[], int n, int num) {int index;vector<double>result;for (int i = 0; i < n; i++){index = arr.find(num - arr[i]);if (index != NULL){result.push_back(arr[i]);result.push_back(arr[index]);break;}}return result; }
解法三?
還可以換個角度來考慮問題，假設已經有了這個數組的任意兩個元素之和的有
序數組（長為N^2）。那么利用二分查找法，只需用O（2*log2N）就可以解決這個
問題。當然不太可能去計算這個有序數組，因為它需要O（N^2）的時間。但這個思
考仍啟發我們，可以直接對兩個數字的和進行一個有序的遍歷，從而降低算法的時
間復雜度。?
首先對數組進行排序，時間復雜度為（N*log2N）。?
然后令i = 0，j = n-1，看arr[i] + arr[j] 是否等于Sum，如果是，則結束。如果小于
Sum，則i = i + 1；如果大于大于Sum，則 j = j – 1。這樣只需要在排好序的數組上遍
歷一次，就可以得到最后的結果 ，時間復雜度為O（N）。兩步加起來總的時間復雜
度O（N*log2N），下面這個程序就利用了這個思想，代碼如下所示:

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

總結

以上是生活随笔為你收集整理的快速寻找满足条件的两个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。