1.Two Sum
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].
2.兩數(shù)之和
給定一個整數(shù)數(shù)組，返回兩個數(shù)字的索引雾叭，要求兩個數(shù)字加起來等于一個特定的目標(biāo)值悟耘。
你可以假定每個輸入只有一個解決方案，并且不能使用同一個元素兩次织狐。
例子：
給定nums = [2暂幼，7，11移迫，15]旺嬉，target=9，
因為nums[0] + nums[1] = 2 + 7 = 9起意，
返回[0, 1]鹰服。
3.說明
這道Two Sum的題目作為LeetCode的開篇之題，
乃是經(jīng)典中的經(jīng)典，
正所謂"平生不識TwoSum悲酷，刷盡LeetCode也枉然"套菜。
下面我將分析幾種常見的解法，
循序漸進(jìn)的寫出越來越優(yōu)的解法设易，
并且給出Java實現(xiàn)代碼逗柴，
同時分析算法的時間復(fù)雜度。
4.窮舉法
遍歷所有的兩個數(shù)字的組合顿肺，然后計算兩數(shù)和戏溺，
兩個for循環(huán)搞定，簡單暴力屠尊，比較費時的解法旷祸，
這個算法的時間復(fù)雜度是O(n^2)。
public int[] twoSumV1(int[] nums, int target) {
int[] results = new int[2];
for (int i = 0; i < nums.length; i++) {
// 注意j從i的下一個位置開始讼昆，同一個元素不能重復(fù)使用
for (int j = i + 1; j < nums.length; j++) {
// 兩數(shù)和等于目標(biāo)值即可退出查找
if (nums[i] + nums[j] == target) {
results[0] = i;
results[1] = j;
return results;
}
}
}
return results;
}
5.排序雙指針夾逼法
先從小到大對數(shù)組進(jìn)行排序托享，
再用雙指針夾逼求出，
左邊的指針left指向數(shù)組開始位置浸赫，對應(yīng)數(shù)組的最小值闰围，
右邊的指針right指向數(shù)組結(jié)束位置，對應(yīng)數(shù)組的最大值既峡，
兩數(shù)相加后sum和目標(biāo)值target比較羡榴，
如果sum<target，則指針left向右邊較大的數(shù)移動一位运敢，
如果sum>target校仑，則指針right向左邊較小的數(shù)移動一位，
直到sum=target者冤，獲得題目所需要的解肤视，
注意需要使用Map記錄原來的數(shù)字對應(yīng)的索引位置，
這里要求數(shù)組里面的整數(shù)不能重復(fù)涉枫。
這個算法的時間復(fù)雜度是O(n)邢滑。
public int[] twoSumV2(int[] nums, int target) {
int[] results = new int[2];
//記錄原來的數(shù)對應(yīng)的索引位置
Map<Integer, Integer> value2index = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// nums中不能有重復(fù)的數(shù)字，否則只會記錄最后一個數(shù)字的索引
value2index.put(nums[i], i);
}
// 從小到大對數(shù)組進(jìn)行排序
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
// 兩數(shù)和等于目標(biāo)值即可退出查找
if (sum == target) {
// 獲取當(dāng)前兩個數(shù)在原數(shù)組索引位置
results[0] = value2index.get(nums[left]);
results[1] = value2index.get(nums[right]);
return results;
}
// 兩數(shù)和小于目標(biāo)值愿汰，則指針left向右邊較大的數(shù)移動一位
if (sum < target) {
left++;
}
// 兩數(shù)和大于目標(biāo)值困后，則指針right向左邊較小的數(shù)移動一位
if (sum > target) {
right--;
}
}
return results;
}
6.Map空間換時間法
這個解法相對于上一個解法更進(jìn)一步，
Map不僅用來查找數(shù)值對應(yīng)的索引位置衬廷，
而且能夠用來判斷數(shù)值是否存在于數(shù)組中摇予，
由于使用的是HashMap，
不會增加算法的時間復(fù)雜度吗跋，
而且不用要求數(shù)組里面的整數(shù)不能重復(fù)侧戴，
因為如果有重復(fù)的兩個數(shù)字A1,A2宁昭，
1和2分別代表數(shù)組在數(shù)組中的索引，
Map中記錄了數(shù)字A最后的索引2酗宋，
然后遍歷A1時正好能取出索引2,
此刻會立即返回結(jié)果积仗，
不會進(jìn)行后續(xù)查找。
首先使用Map記錄數(shù)字對應(yīng)的索引位置蜕猫，
然后我們只需要遍歷一遍數(shù)字a寂曹，
另外一個數(shù)字b通過target-a得到，
然后在Map中查找是否存在b回右，
如果存在隆圆，則使用當(dāng)前數(shù)字a的索引,
以及在Map中找出b的索引即可。
注意查找到的數(shù)字b不能是第一個數(shù)字a翔烁，
即兩個數(shù)字ab對應(yīng)的索引位置不能相同渺氧。
這個算法的時間復(fù)雜度是O(n)。
public int[] twoSumV3(int[] nums, int target) {
int[] results = new int[2];
// 記錄數(shù)字對應(yīng)的索引位置
Map<Integer, Integer> value2index = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
value2index.put(nums[i], i);
}
// 只遍歷一個數(shù)字a
for (int i = 0; i < nums.length; i++) {
Integer a = nums[i];
Integer b = target - a;
// 判斷數(shù)字b是否存在蹬屹，且b的索引不和a相同
if (value2index.containsKey(b) && value2index.get(b) != i) {
results[0] = i;
// 獲取b在數(shù)組中的索引位置
results[1] = value2index.get(b);
break;
}
}
return results;
}
7.Map空間換時間法優(yōu)化
把兩個for循環(huán)合并成一個阶女，
一邊遍歷a，一邊初始化Map哩治，
由于當(dāng)前遍歷的a還沒有加入到Map中，
所以不會出現(xiàn)b和a的索引相同的情況衬鱼，
而且能夠正好窮盡a和b的組合业筏，
為了更好的理解該算法優(yōu)化，
下面舉例鸟赫，僅作參考蒜胖，而非實際實現(xiàn)，
算法改進(jìn)前：
[1,2,3]對應(yīng)的組合[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]
算法改進(jìn)后：
[1,2,3]對應(yīng)的組合[2,1],[3,1],[3,2]
所以該算法仍然能夠正確工作抛蚤。
這個算法的時間復(fù)雜度仍然是O(n)台谢。
程序輸出的結(jié)果正好和上面的相反，
假設(shè)nums=[1,2,3]岁经，target=3,
算法改進(jìn)前：
results=[0,1]朋沮，對應(yīng)組合[1,2]；
算法改進(jìn)后：
results=[1,0]缀壤，對應(yīng)組合[2,1]樊拓；
public int[] twoSumV4(int[] nums, int target) {
int[] results = new int[2];
Map<Integer, Integer> value2Index = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer a = nums[i];
Integer b = target - a;
// 判斷數(shù)字b是否存在,存在即可退出查找
if (value2Index.containsKey(b)) {
results[0] = i;
results[1] = value2Index.get(b);
break;
}
// 在判斷之后再把a加入map
value2Index.put(a, i);
}
return results;
}
8.參考
[LeetCode] 1. Two Sum 兩數(shù)之和
求和問題總結(jié)(leetcode 2Sum, 3Sum, 4Sum, K Sum)
