摘要：如果存在该差值，说明存在两个数之和是目标和。而哈希表方法中的则可以换成。如果要求的不是两个数和和，而是找两个数之差为特定值的配对呢同样用哈希表可以解决。
Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.暴力法 Brute Force 复杂度The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
O(1)空间 O(n^2)时间
思路通过双重循环遍历数组中所有元素的两两组合，当出现符合的和时返回两个元素的下标
注意内层循环要从外层循环下标加一开始，避免遍历到两个相同的元素
代码public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
if(nums.length < 2){
return result;
}
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 + 1;
result[1] = j + 1;
return result;
}
}
}
return result;
}
}
哈希表 Hash Table
复杂度
O(n)空间 O(n)时间
思路第一次遍历数组先将所有元素和它的下标作为key-value对存入Hashmap中，第二次遍历数组时根据目标和与当前元素之差，在Hashmap中找相应的差值。如果存在该差值，说明存在两个数之和是目标和。此时记录下当前数组元素下标并拿出Hashmap中数组元素下标即可。Hashmap获取元素的时间复杂度是O(1)，所以总的时间复杂度仍不超过O(n)。
注意判定是否存在该差值时，要同时判断该差值的下标是不是当前遍历的元素下标，以避免重复
哈希表作为一个Collection，初始化时请注意声明Key和Value的类型
代码public class Solution {
public int[] twoSum(int[] nums, int target) {
Map map = new HashMap();
int[] res = new int[2];
for(int i = 0; i < nums.length; i++){
int diff = target - nums[i];
if(map.containsKey(nums[i])){
res[0] = map.get(nums[i]) + 1;
res[1] = i + 1;
}
map.put(diff, i);
}
return res;
}
}
2018/2 更新
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
numsMap = {}
for index in range(0, len(nums)):
num1 = nums[index]
num2 = target - num1
if num2 in numsMap:
return [index, numsMap[num2]]
else:
numsMap[num1] = index
2018/10
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
result := make([]int, 2)
for i := 0; i < len(nums); i++ {
var curr = nums[i]
var diff = target - curr
result[0] = i
if _, ok := m[diff]; ok {
result[1] = m[diff]
return result
} else {
m[curr] = i
}
}
return result
}
排序双指针法 Sorting with Two Pointers
复杂度
O(n)空间 O(nlogn)时间
思路首先将原数组复制一遍，对新数组进行排序。排序后将双指针指向头部与尾部元素，进行迭代。如果双指针指向元素之和大于目标和，则将尾部指针向前移一位，反之则将头部指针向后移一位，直到双指针指向元素之和等于目标和，记录这两个元素的值，然后再遍历一遍旧数组，找出这两个元素的下标。
注意该方法需要先将结果数组都初始化为-1，否则在遍历旧数组时无法去除重复，可能会将两个下标都存入同一个结果中
代码
