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)遍歷兩次墙贱，依次記錄兩個位置的值，這樣自然是可以解的，但是這種解的時間復雜度為O(n^2),不過試了一下善玫，這種解法也能過工窍，代碼就不上了科乎。我們來分析能否降低算法復雜度壁畸，將其降到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的底層實現(xiàn)走敌，當我們遍歷到當前值nums[i]的時候碴倾，來查詢map是否還有target-nums[i]這個鍵，如果有的話掉丽，則找出對應的值跌榔，否則我們將當前的nums[i]作為鍵，位置i作為值放進數(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;
}
