ACM之兩數之和問題

題目以下：java

大概的意思是：給咱們一個Int型的數組和一個目標值，找出數組中兩個值之和爲目標值的元素位置；要求是每一個輸入對應一個答案（即找到符合條件的元素直接返回結果就行，不用繼續日後找，難度下降）而且相同的元素值不能用兩次。面試

1.剛開始的思路： 數組

      偉大而又萬能的蠻力法，用兩個for循環，很容易求解，時間複雜度爲O(N^2)，代碼以下：數據結構

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for(int i = 0;i < nums.length;i++){
            for(int j = i+1;j < nums.length;j++){
                if((nums[i]+nums[j]) == target){
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }
}

2.優化解法ide

    蠻力法雖然是我這種菜鳥的最愛，惋惜不是面試官要的答案，仍是不能將就的。想辦法把時間複雜度將爲O(N)就很爽了啊，也就是把上面蠻力法中的一個for循環給去掉，怎麼弄呢？蠻力法的思路是不斷地進行a+b去匹配目標值c，既然目標值知道，那咱們固然能夠選擇c-b去匹配a。用一個for循環將c-b的值存在一個數據結構中，而後查找這個數據結構中是否含有a就行。那麼問題來了，這個數據結構選什麼呢：數組？棧？隊列仍是HashMap？一看前面三種選擇查找的時間複雜度仍是O(N)，而HashMap查找的時間複雜度爲O(1)，那確定選HashMap，問題都搞定了，代碼實現出來就OK：優化

public class TwoSumBter {
    public static int[] twosum(int[] num,int target){
        int[] res = new int[2];
        int len = num.length;
        //判斷輸入數組的大小
        if(num == null || num.length<2){
            res[0] = 0;
            res[1] = 0;
            return res;
        }
        //創建HashMap
        HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
        
        for(int i=0;i<len;i++){
        //判斷HashMap中是否含有目標數組中的數
            if(hm.containsKey(num[i])){
                res[0] = hm.get(num[i]);
                res[1] = i;
                
                return res;
            }else{
                hm.put((target-num[i]), i);
            }
        }    
        return new int[]{0,0};    
    }
}