? ? 很多程序員都愛犯的一個(gè)毛病加酵，就是剛開始動(dòng)手寫代碼就想找到最優(yōu)解因痛，對(duì)那些已經(jīng)被人解決過的問題饮醇，還可以通過網(wǎng)絡(luò)獲取最優(yōu)化的解決方案，當(dāng)進(jìn)入一個(gè)全新的領(lǐng)域髓帽，這種想畢其功于一役的想法會(huì)限制人的能力菠赚，推遲項(xiàng)目進(jìn)度。
更一般的做法是：
1)先分析問題郑藏，找到一個(gè)可行的方案
2)將方案落地
3)思考當(dāng)問題規(guī)模增大一個(gè)量級(jí)（10倍）時(shí)，這套方案能在可接受的時(shí)間內(nèi)給出問題答案嗎
4）如果隨著問題規(guī)模不斷增長(zhǎng)瘩欺，方案不能在期望時(shí)間內(nèi)給出問題答案必盖，我們就要分析，那一塊兒出現(xiàn)了性能瓶頸俱饿，優(yōu)化它
5) 就這樣不斷優(yōu)化方案歌粥，直到處理能力達(dá)到數(shù)學(xué)規(guī)定的上界，就有了最優(yōu)解
來看一個(gè)twoSum問題：
輸入一個(gè)數(shù)組拍埠，找出數(shù)組中和為0的數(shù)字對(duì)之和失驶。
先給出一個(gè)簡(jiǎn)單的方案：使用暴力枚舉法，粗獷枣购，但是能解決小規(guī)模問題
public class TwoSum {
? ? public static int twoSum(int[] arr){
? ? ? ? int cnt = 0;
? ? ? ? for(int i = 0; i < arr.length; i++)
? ? ? ? ? ? for(int j = i + 1; j < arr.length; j++)
? ? ? ? ? ? ? ? if(arr[i] + arr[j] == 0)
? ? ? ? ? ? ? ? ? ? cnt++;
? ? ? ? return cnt;
? ? }
? ? public static void main(String[] args) {
? ? ? ? int[] arr = {1,-1,0,2,-2,3,-3,5,6,7,-7};
? ? ? ? System.out.println(TwoSum.twoSum(arr));
? ? }
這個(gè)方案的復(fù)雜度是嬉探，隨著問題規(guī)模不斷增大擦耀，性能會(huì)越來越差，難以滿足需求涩堤，那就想辦法將其復(fù)雜度降為
眷蜓，即問題轉(zhuǎn)化為將一個(gè)n降為
。我們知道二分法可以實(shí)現(xiàn)這種需求：
public class BinarySearch {
? ? public static int rank(int key, int[] arr) {
? ? ? ? if(arr == null || arr.length == 0) {
? ? ? ? ? ? return -1;
? ? ? ? }
? ? ? ? int high = arr.length - 1;
? ? ? ? int low = 0;
? ? ? ? while(low <= high) {
? ? ? ? ? ? int mid = low + (high -low)/2;
? ? ? ? ? ? if(arr[mid] == key){
? ? ? ? ? ? ? ? return mid;
? ? ? ? ? ? }
? ? ? ? ? ? if(arr[mid] > key) {
? ? ? ? ? ? ? ? high = mid - 1;
? ? ? ? ? ? }
? ? ? ? ? ? if(arr[mid] < key) {
? ? ? ? ? ? ? ? low = mid + 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }
? ? public static void main(String[] args) {
? ? ? ? int[] arr = {1,2,3,4,5,6,7,-1,10,15};
? ? ? ? System.out.println(BinarySearch.rank(5, arr));
? ? }
利用二分法來改進(jìn)算法：
public class TwoSumFast {
? ? public static int twoSumFast(int[] arr){
? ? ? ? int cnt = 0;
? ? ? ? Arrays.sort(arr);
? ? ? ? for(int i = 0; i < arr.length; i++) {
? ? ? ? ? ? if(BinarySearch.rank(-arr[i], arr) > i) {
? ? ? ? ? ? ? ? cnt++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return cnt;
? ? }
? ? public static void main(String[] args) {
? ? ? ? int[] arr = {1,-1,0,2,-2,3,-3,5,6,7,-7};
? ? ? ? System.out.println(TwoSumFast.twoSumFast(arr));
? ? }
須知胎围，如果a[i] + a[j] = 0,那么a[j] = -a[i],即遍歷數(shù)組吁系，如果存在-a[i],那么一定存在滿足twoSum規(guī)則的子數(shù)組。
那么還有比這種防范更快的算法嗎白魂？數(shù)學(xué)上可以證明汽纤，沒有，這是最優(yōu)解了福荸。
最后冒版，要明白一點(diǎn)：一個(gè)能不斷演化的算法更有價(jià)值，一個(gè)能不斷成長(zhǎng)的人生更有意義逞姿！
