1.兩數(shù)之和
給定一個整數(shù)數(shù)列壹甥，找出其中和為特定值的那兩個數(shù)碘饼。
你可以假設(shè)每個輸入都只會有一種答案烁峭，同樣的元素不能被重用。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解題思路
第一反應(yīng)將數(shù)組中的數(shù)兩兩相加郊尝，找到等于目標(biāo)值的2個數(shù)就是我們要的解二跋。注意數(shù)字不能被使用2遍，所以第二層循環(huán)要從i+1開始
public int[] twoSum(int[] nums, int target) {
int[] result = 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) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
但是其實(shí)如果我們換一個思考問題的方式會有更簡便的方法流昏，a+b=c
a = c - b; 在加上文中的提示 數(shù)組元素不會重復(fù)扎即。所以我們可以使用Map來進(jìn)行加速。Map的key為數(shù)組中的值况凉，map的value為數(shù)組下標(biāo)谚鄙。當(dāng)前數(shù)組是a時只需要找到key為b的值就好。
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer,Integer> map = new HashMap<>(nums.length);
for (int i = 0; i < nums.length; i++) {
int value = target-nums[i];
Integer index = map.get(value);
if (index != null && index != i) {
result[0] = i;
result[1] = index;
break;
}
map.put(nums[i],i);
}
return result;
}
在日常工作中刁绒，我們有很多需要用多重循環(huán)才能解決的問題都能被Map這種處理方式所替代闷营，以提高程序運(yùn)行的效率。
LeetCode地址:https://leetcode-cn.com/problems/two-sum/description/
