Leetcode经典题17--两数之和
两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
输入输出示例
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
解题方案
方式一：哈希表
算法思想
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。如果存在target - x，则直接输出结果
实现代码
class Solution {
public int[] twoSum(int[] nums, int target) {
//遍历元素，如果target-num[i]不在表中，那么就将元素添加到哈希表当中，如果在，返回下标
int len = nums.length;
Map<Integer, Integer> hashMap = new HashMap<>(len - 1);//在创建哈希表时，尽量指定哈希表的容量
//执行到最后一个元素时，如果哈希表当中还是没有，那么就没有了
for (int i=0;i<len;i++){
int another=target-nums[i];
if(hashMap.containsKey(another)){
return new int[]{hashMap.get(another),i};
}else{
hashMap.put(nums[i],i);
}
}
return nums;
}
}复杂度分析
时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。
两数之和Ⅱ -输入有序数组
题目描述：
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
输入输出示例
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
解决方案
方式一：二分查找
算法思想
在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。
实现代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; ++i) {
//固定第一个数的值
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
//在第一个数的右侧找第二个数，使用二分查找的方式
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return new int[]{-1, -1};
}
}复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)，寻找第二个数使用二分查找，时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。
空间复杂度：O(1)。
方式二：双指针
算法思想
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。
使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。
假设 numbers[i]+numbers[j]=target 是唯一解，其中 0≤i
如果左指针先到达下标 i 的位置，此时右指针还在下标 j 的右侧，sum>target，因此一定是右指针左移，左指针不可能移到 i 的右侧。
如果右指针先到达下标 j 的位置，此时左指针还在下标 i 的左侧，sum
由此可见，在整个移动过程中，左指针不可能移到 i 的右侧，右指针不可能移到 j 的左侧，因此不会把可能的解过滤掉
实现代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
//开始时，左右指针位于数组的首尾
int low = 0, high = numbers.length - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[]{low + 1, high + 1};
} else if (sum < target) {
//如果总和比目标值小，则需要变大，左指针右移
++low;
} else {
//如果总和比目标值大，则需要变小，对于有序数组，右指针左移
--high;
}
}
return new int[]{-1, -1};
}
}复杂度分析
时间复杂度：O(n)，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
空间复杂度：O(1)。
主要参考Leetcode官方题解