不積硅步無以至千里

leetcode題庫第一題——兩數(shù)之和
給定一個整數(shù)數(shù)組和一個整數(shù)目標(biāo)值，返回兩個數(shù)的下標(biāo)，這兩個數(shù)相加和為目標(biāo)值。
條件1：假定給定的數(shù)組中最多有一組數(shù)據(jù)滿足條件。
條件2: 數(shù)組中的元素每個只能使用一次。
條件3: 可以以任意順序返回兩個元素的下標(biāo)。

暫時有兩種解決辦法：
一、省時間
解決思路： 先從頭到尾遍歷數(shù)組，取到第一個元素之后遍歷第一個元素之后的元素，然后判斷兩數(shù)之和是否為target，如果找到了，就保存這兩個數(shù)的下標(biāo)，返回結(jié)果，如果沒有找到，就繼續(xù)查找下一個元素，再進行判斷，如果都遍歷完了還沒有找到和為target的值，就返回{-1,-1}。
時間復(fù)雜度 o(n2)，空間復(fù)雜度o(n),

/**
     * @param target   目標(biāo)和
     * @param orgArray 找查找的數(shù)組
     * @return 符合條件的下標(biāo)
     */

    public int[] searchNum(int target, int[] orgArray) {
        int[] result = {-1, -1};
        for (int i = 0; i < orgArray.length; i++) {
            for (int j = i + 1; j < orgArray.length; j++) {
                if (orgArray[i] + orgArray[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }

二、省空間
解決思路：用一個hashMap來存儲整數(shù)數(shù)組的元素和對應(yīng)的下標(biāo)（key存儲元素，value存儲元素對應(yīng)的下標(biāo)），然后遍歷數(shù)組，判斷map中是否存在target - orgArray[i]這樣的key，如果存在，就返回map中對應(yīng)key 的value（對應(yīng)元素的下標(biāo)）和i。
如果我自己寫，可能會遍歷兩次，第一次遍歷構(gòu)造map，第二次遍歷判斷。官方解法中把兩次判斷和在一起同樣可以實現(xiàn)，節(jié)省了代碼的行數(shù)。在以后要寫兩次遍歷的時候，可以考慮一下是不是可以用一次遍歷實現(xiàn)。
如果想要節(jié)省數(shù)組查找的時間，可以考慮用HashMap來實現(xiàn)。
時間復(fù)雜度：o(n)
空間復(fù)雜度：o(n)

/**
     * 通過hash表來實現(xiàn)
     *
     * @param target
     * @param orgArray
     * @return
     */
    public int[] searchNum2(int target, int[] orgArray) {

        HashMap hashmap = new HashMap<Integer, Integer>();
        for (int i = 0; i < orgArray.length; i++) {
            if (hashmap.containsKey(target - orgArray[i])) {
                return new int[]{(int) hashmap.get(target-orgArray[i]), i};
            }
            hashmap.put(orgArray[i], i);
        }
        return new int[0];
    }