Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15],

target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,

return [0,1].

題目分析：要求求出一個數(shù)組中兩個元素和為一個定值的問題，我們的第一想法自然是循環(huán)遍歷兩次，依次記錄兩個位置的值，這樣自然是可以解的，但是這種解的時間復(fù)雜度為O(n^2),不過試了一下，這種解法也能過，代碼就不上了。我們來分析能否降低算法復(fù)雜度，將其降到O(n)級別，我們?nèi)绻胍淮螔呙杈湍艿玫秸_結(jié)果的話，自然需要一個數(shù)據(jù)結(jié)構(gòu)來記錄之前掃描過的數(shù)據(jù)，然后判斷這兩個值的和是否為target，這里我們自然而然的可以想到用Map數(shù)據(jù)結(jié)構(gòu)來存儲已經(jīng)遍歷過的值和它的位置，PS：HashMap的查詢效率是O(1)而不是O(n)，如果對于這個不了解的話可以去看一下hashMap的底層實(shí)現(xiàn)，當(dāng)我們遍歷到當(dāng)前值nums[i]的時候，來查詢map是否還有target-nums[i]這個鍵，如果有的話，則找出對應(yīng)的值，否則我們將當(dāng)前的nums[i]作為鍵，位置i作為值放進(jìn)數(shù)組返回。代碼如下:

public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[0]=map.get(target-nums[i]);
                result[1]=i;
            } else {
                map.put(nums[i], i);
            }
        }
        return result;
    }