1五督、問題
給定一個整數(shù)數(shù)組和一個目標值藏否，找出數(shù)組中和為目標值的兩個數(shù)。
你可以假設(shè)每個輸入只對應(yīng)一種答案概荷，且同樣的元素不能被重復(fù)利用秕岛。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
2、思路
- 思路1： 兩個循環(huán)误证，遍歷兩次解決我問題继薛，時間復(fù)雜度O(n2)
- 思路2：先排序，再從兩端（low,high）向中間靠近愈捅，兩數(shù)和大于目標值high--遏考，兩數(shù)和小于目標值low++，時間復(fù)雜度o(logn)
- 思路3：兩次循環(huán)：
第一次：數(shù)組轉(zhuǎn)HashMap<value,index>蓝谨，
第二次循環(huán)灌具，循環(huán)值存入tmp：通過target與tmp在map中獲取到值，且獲取到的index與當前數(shù)據(jù)index值不等譬巫，兩次循環(huán)咖楣，時間復(fù)雜度O（n） - 思路4：是思路3的升級，一次循環(huán)搞定：
初始空map芦昔，target與tmp差值在map中獲取到值诱贿，則成功返回；
否則將目tmp和index存入map中咕缎，時間復(fù)雜度O（n）珠十，較思路3時間更短
3、思路4的實例（java）
public static int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int index1 = 0; index1 < nums.length; index1++) {
Integer sTarget = target - nums[index1];
Integer index2 = map.get(sTarget);
if (index2 != null && index1 != index2) {
int result[] = {index2, index1};
return result;
}
map.put(nums[index1], index1);
}
return null;
}
