描述
给出一个整数数组，请在数组中找出两个加起来等于目标值的数，
你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的
假设给出的数组中只存在唯一解
例如：
给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2
示例1
输入：
[3,2,4],6
复制返回值：
[2,3]
复制说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以输出[2,3]
方法一：直接遍历
具体做法：
循环遍历数组的每一个数，如果遍历的两数之和等于target，则返回两个数的下标；
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int n = numbers.length;
int[] res = {-1, -1};
//遍历数组
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
//判断相加值是否为target
if (numbers[i] + numbers[j] == target) {
res[0] = i+1;
res[1] = j+1;
//返回值
return res;
}
}
}
return res;
}
}
|
复杂度分析：
- 时间复杂度：O(n^2) 遍历两次数组
- 空间复杂度：O(1) 未申请额外空间
方法二 hash表
具体做法：
使用Map来降低时间复杂度，遍历数组，如果没有 （target - 当前值） 就将当前数字存入哈希表，如果有，返回该数字下标即可。
哈希表可以优化第二遍循环中对元素的检索速度，
具体过程如下图所示：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
HashMap<Integer, Integer> map = new HashMap<>();
//遍历数组
for (int i = 0; i < numbers.length; i++) {
//将不包含target - numbers[i]，装入map中，包含的话直接返回下标
if(map.containsKey(target - numbers[i]))
return new int[]{map.get(target - numbers[i])+1, i+1};
else
map.put(numbers[i], i);
}
throw new IllegalArgumentException("No solution");
}
}
|