00001 两数之和
题目描述
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9， 所以返回 [0, 1]
力扣地址
解题报告
暴力法
本题解由微信公众号
小猿刷题提供, 错误之处, 欢迎指正.
暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target−x 相等的目标元素.
/**
* 微信公众号"小猿刷题"
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
哈希表
本题解由微信公众号
小猿刷题提供, 错误之处, 欢迎指正.
为了优化运行时间复杂度，引入哈希表来检查数组中是否存在目标元素。如果存在，则找出它的索引。
/**
* 微信公众号"小猿刷题"
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
// 数字原始和其对应的下标映射
Map<Integer, Integer> map = new HashMap<>();
// Hash表中检测是否存在匹配
for(int i=0; i< nums.length; i++){
int num = target - nums[i];
if(map.containsKey(num)){
return new int[]{map.get(num), i};
} else {
map.put(nums[i], i);
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
小猿刷题
00167 两数之和 II - 输入有序数组
题目描述
给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
- 返回的下标值(
index1和index2)不是从零开始的。 - 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
力扣地址
- https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
- https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
解题报告
哈希表
本题解由微信公众号
小猿刷题提供, 错误之处, 欢迎指正.
遍历数组，数组遍历的当前值为 nums[i]，那么 y 应该是 target - nums[i]; 所以只要在遍历的时候确定 target - nums[i] 在数组里有，返回对应下标.
/**
* 微信公众号"小猿刷题"
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap();
for(int i = 0; i < nums.length; i ++){
int cur = nums[i];
int num = target - cur;
if(map.containsKey(num)){
return new int[] {map.get(num) + 1, i + 1};
} else {
map.put(cur, i);
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
双指针
本题解由微信公众号
小猿刷题提供, 错误之处, 欢迎指正.
我们使用两个指针，初始分别位于第一个元素和最后一个元素位置，比较这两个元素之和与目标值的大小。
如果和等于目标值，我们发现了这个唯一解。如果比目标值小，我们将较小元素指针增加一。如果比目标值大，我们将较大指针减小一。移动指针后重复上述比较知道找到答案。
/**
* 微信公众号"小猿刷题"
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
if (nums[low] + nums[high] == target) {
return new int[] {low + 1, high + 1};
}
if (nums[low] + nums[high] < target) {
low ++;
} else {
high --;
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
小猿刷题
