摘要：如果沒有，就到里面復雜度分析就是，因為只掃了一遍數組。復雜度分析當然就是最壞情況了，也是標準的雙指針復雜度。復雜度分析這種題應該不太需要分析復雜度吧，能實現就行。復雜度分析還是最后再說兩句所以可以看出，很多題目思路一致，換湯不換藥。

友情提示：篇幅較長，找題目的話，右邊有目錄，幸好我會MarkDown語法。
改成了系列模式，因為類似的題不少，本質上都是換殼，所以在同一篇文章里面把這類問題匯總一下。先說2 Sum。這道題非常出名，因為這是leetcode的第一道題。很多人說一些公司招聘的時候，這道題專門出給他們想招進來的人，因為這不是放水，簡直就是洪水。要做的就是已知一個數組，和一個target值。返回兩個目標的index，這兩個目標求和就是target值。

這題不難，只需要熟悉hashtable即可。在hashtable里面，key是差，value是index。比如例子中的[2,7,11,15],target是9。那么在2的時候就存入7 0，下一位找到7的時候，之前有個差值是7，那么就返回7對應的index，0，以及當前這個7的index，就是1。

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        //創建一下數組，要存兩個index的數組。
        int[] result = new int[2];
        //這里用hashtable也行，看心情。
        Map map = new HashMap();
        //掃一遍數組，一邊掃一邊存
        for(int i = 0; i < nums.length; i++){
            int cur = nums[i];
            //這里搞出來個差值，其實差值是在沒找到之后添加到map里面的。
            int toFind = target - cur;
            //如果發現之前需要這個差值，那就找index。
            if(map.containsKey(cur)){
                result[0] = map.get(cur);
                result[1] = i;
                return result;
            }
            //如果沒有，就put到map里面
            else{
                map.put(toFind, i);
            }
        }
        return result;
    }
}

就是O(n)，因為只掃了一遍數組。

雖然這題非常簡單，但是14年秋天第一次看到這題的時候感覺還是難到爆炸，無從下手。因為一絲編程基礎都沒有，現在兩年過去了，用腳趾都能敲出來。其實行業之間努力其次，路徑非常重要，在這里感謝一下點撥我的老鄉和兄弟們。而且重新寫了幾次，連變量命名都是一樣的。

這題用sorted當做題目，好比路邊的一些職業勾引男性行人，非常直接的就意味著二分搜索。一次查一半，所以剛開始只用到了二分搜索。但是有個問題，二分搜索的步子太大，可能把目標值跳過，那么還要借鑒雙指針的全盤掃描的特點。

public class Two_Sum_II {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        //這里用二分搜索，我常用start和end來命名兩頭，middle是中間。
        int start = 0;
        int end = numbers.length-1;
        //這個while循環條件很巧妙，二分搜索建議固定一個模板，這個就挺好固定的。
        while (start + 1 < end) {
            //看，我剛說的是實話，而且這里middle的計算方法是防止越界。
            int middle = start + (end-start)/2;
            if (numbers[start] + numbers[end] < target) {
                //這里需要判斷，到底是跳一半還是走一步，就再加個判斷。
                if (numbers[middle] + numbers[end] < target) {
                    start = middle;
                }
                else {
                    start++;
                }
            }
            else if(numbers[start] + numbers[end] > target) {
                if (numbers[middle] + numbers[start] > target) {
                    end = middle;
                }
                else {
                    end--;
                }
            }
            else {
                break;
            }
        }
        //題目中保證了有結果，還不是zero-based，那么就把result兩項都續一秒。
        result[0] = start+1;
        result[1] = end+1;
        return result;
    }
}

當然就是最壞情況O(n)了，也是標準的雙指針復雜度。不過二分搜索方法是它最優情況是O(nlgn)。

不得不說，這個題目把二分搜索和雙指針拼在一起非常有創意。只用二分搜索讓我多交了一個submit，好題一個。

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

鎖住的題，罕見的一道design題目和Google沒關系，tag只有Linkedin，怪不得被收購了。

這是一道入門級別的design題目，當然第一次遇到design這個詞我就像腦血栓般渾身發抖。不過好在它脫胎于Two Sum，本質上還是不難的，我們要做的就是套上design的外殼，解決掉它。值得注意的是，一個數字只能用1次，所以還是要記錄一下數字出現的次數的。

public class TwoSumIII {
    //用一個List當容器裝數字，用Map來記錄數字出現的次數
    List list = new ArrayList<>();
    Map map = new HashMap();
    // Add the number to an internal data structure.
    public void add(int number) {
        list.add(number);
        //非常常規的往map里記錄出現個數的寫法
        if (map.containsKey(number)) {
            map.put(number, map.get(number)+1);
        }
        else {
            map.put(number,1);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (int i = 0; i < list.size(); i++) {
            int cur = list.get(i);
            int toFind = value - cur;
            //這里還是Two Sum的求法，取一個，找另一個。值得注意的是需要看求和的兩個數是不是相等。
            if (cur != toFind) {
                //根據leetcode測試，在map里面找比在list找目標數字更快一些。
                if (map.containsKey(toFind)) {
                    return true;
                }
            }
            else {
                if (map.get(cur) > 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

這種題應該不太需要分析復雜度吧，能實現就行。每次都是遍歷一遍List，所以就是O(n)。

寫的時候發現其實遍歷一下Map也行，可以省去一個list。但我偏偏不省，因為List不要錢，能加就加，而且看著也方便，一個map用于不同的用途，可能會引起線程沖突。出來混，多一事不如少一事。

這題用腳后跟看都是2Sum的follow up。就是在一個數組里面挑3個數字，這三個數字的和為0就行。需要注意的是triplet這個單詞的拼寫和發音，還有不能有重復的triplet，不能重復這一點還是有點兒小麻煩的

既然是follow up，解決思路也就是follow up。follow up是什么意思呢，我們翻譯一下，follow就是跟隨，up就是上面。就是跟隨上面的意思，我們往上看，上面只有2Sum一題，那我們就跟隨一下。A+B是2Sum，A+B+C是3Sum，那么稍加修改A+(B+C)就成了這兩道題連接的橋梁。所以這題的基本思路就是套了個殼子而已。
值得一提的是，此題可能有重復數字，而且要求不能有重復結果，所以使用雙指針法。前面這句的不是很理所當然，在這里就當經驗記錄一下了，強行解釋就是指針可以跳過重復的數字，而且求和也很容易。

public class ThreeSum {
    public List> threeSum(int[] nums) {
        //首先把輸出寫出來
        List> result = new ArrayList<>();
        //雙指針出馬之前數組通常需要排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            //這個本意是重復數字的話可以跳過。因為之前的數字已經打頭過了，重復的就沒必要打頭了。
            if (i > 0 && cur == nums[i-1]) {
                continue;
            }
            //雙指針出馬，這里注意了我一般命名成left和right。
            int left = i+1;
            int right = nums.length-1;
            //這里注意了開始2Sum過程。
            while (left < right) {
                int two_sum = nums[left] + nums[right];
                if (two_sum < -1*cur) {
                    //說明加和小了，那把左指針往右移動
                    left++;
                }
                else if (two_sum > -1 * cur) {
                    //大了那就往左移動
                    right--;
                }
                else {
                    List list = new ArrayList<>();
                    list.add(cur);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    //把這次記錄的結果加到result里面
                    result.add(list);
                    //下回測試corner case的時候就一群0，這次4個0就吃虧了，忘了這個while循環，所以要跳過重復數字。
                    while(left+1 < right && nums[left] == nums[left+1]){
                        left++;
                    }
                    while (right-1 > left && nums[right] == nums[right-1]) {
                        right--;
                    }
                    //跳過之后，繼續挪動一下。
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

這個排序的復雜度是O(nlgn)，循環的復雜度就是O(n^2)，所以就是循環的復雜度n方。

其實這種數組題，無論多么的熟練，都要在紙上先勾畫一下思路，尤其是這道題里面重復數字的處理，其實也可以用個set來去重，但那樣畢竟顏值不行，不符合我自拍的一貫水準。跳過相等數字，最后再挪動一下，code里面不好分析，在紙上畫畫一目了然。

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
  [-2, 0, 1] [-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

這題居然是鎖住的，company tag只有一個Google，所以把題目內容貼上來。

這題說老實話讓我很困惑，為啥這題都能當一道題出了。其實就是3Sum稍微變一下，然后返回個個數而不是一群triplet。而且要求是O(n2)，那類比3Sum的雙指針方法可以滿足。

public class Three_Sum_Smaller {

public int threeSumSmaller(int[] nums, int target) {
    //雙指針是一定要排序的，否則后面根據大小挪動指針就沒有意義了。
    Arrays.sort(nums);
    int result = 0;
    for (int i = 0; i < nums.length-2; i++) {
        int left = i+1;
        int right = nums.length-1;
        int cur = nums[i];
        while (left < right) {
            int two_sum = nums[left] + nums[right];
            //這里需要注意如果滿足條件，接下來不需要移動指針，直接把中間所有的可能性都加起來就可以
            if (cur + two_sum < target) {
                result += right - left;
                left++;
            }
            else {
                //只有和大了，才要讓右邊指針左移，讓整體小一些。
                right--;
            }
        }
    }
    return result;
}

}

直接O(n2)了，就是兩重循環，多說一句，雙指針就是把O(n2)降成O(n)的，外面再套一層循環，就是O(n2)了。

這題會做了，Google是不是能過一輪了啊。就注意小于的情況直接求result就行。

還是一個數組，還有個目標數。返回距離目標最近的一個和，這個和是3個數的和。

和上面一樣，雙指針，看大小。

public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        if(nums == null || nums.length < 3){
            return 0;
        }
        int res = 0;
        int diff = Integer.MAX_VALUE;
        Arrays.sort(nums);

        for(int cur = 0; cur < nums.length-2; cur++){
            int left = cur+1;
            int right = nums.length-1;
            int tempTar = target-nums[cur];
            while(left < right){
                int sum = nums[left] + nums[right];
                int value = Math.abs(sum-tempTar);
                //找到更小的就更新。
                if(value <= diff){
                    diff = value;
                    res = nums[cur] + nums[left] + nums[right];
                }
                if(sum < tempTar){
                    left++;
                    
                }
                else if(sum > tempTar){
                    right--;
                }
                else{
                    return target;
                }
            }
        }
        return res;
    }
}

還是O(n2).

所以可以看出，很多題目思路一致，換湯不換藥。都是雙指針掃數組，非常容易。

這次是4個，就是找四個數，它們的和是目標數。

這次就是3 Sum套了個殼而已，方法都是一樣的。

public class FourSum {
    public List> fourSum(int[] nums, int target) {
        List> res = new ArrayList<>();
        //象征性的說，如果沒有4個數，那還玩個球啊
        if(nums.length < 4) return res;
        //雙指針排序，都看膩了吧
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-3; i++){
            //去掉重復的數字，就是打頭不能相同
            if(i > 0 && nums[i] == nums[i-1]) continue;
            for(int j = i+1; j < nums.length-2; j++){
                //再去掉一遍
                if(j > i+1 && nums[j] == nums[j-1]) continue;
                //實力打臉，以后還是要left和right，low和high太low了。
                int low = j+1, high = nums.length-1;
                while(low < high){
                    int sum = nums[i] + nums[j] + nums[low] + nums[high];
                    if(sum == target){
                        //這里新建一個list也行。
                        res.add(Arrays.asList(nums[i],nums[j], nums[low], nums[high]));
                        while(low+1 < high && nums[low+1] == nums[low]){
                            low++;
                        }
                        while(high-1 > low && nums[high-1] == nums[high]){
                            high--;
                        }
                        low++;
                        high--;
                    }
                    else if(sum < target){
                        low++;
                    }
                    else{
                        high--;
                    }
                }
            }
        }
        return res;
    }
}

O(n3)，因為是三重循環。

這個系列結束了，沒想到從2 Sum可以延伸這么長。不過核心思想都差不多，一些細節處，比如去掉重復數字這種手法需要多加熟練。
這個9月加油找了。