LeetCode_01_TwoSum


1. question: 两数之和(简单)

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/two-sum

示例 1:

1
2
3
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

1
2
输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

1
2
输入:nums = [3,3], target = 6
输出:[0,1]

提示:

1
2
3
4
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

2. answers

思路:

  1. 最简单的直接暴力循环即可,时间复杂度为 O(n^2);

  2. 另一种方法是:数组中的两数之和为target,换句话说就是target减去数组中的某个数,结果一定也是数组中的某个数

    可以利用HashMap(存储数和其下标),将数组中的一部分数存储在HashMap中,然后用target减去数组中的另一部分数,如果差出现在HashMap中,那么这两个数就是要找的结果。

    但是存储哪部分数呢?怎么保证存储的数求和不是target呢?其实可以在遍历的时候,计算差值,如果差值不在HashMap中,那么就说明当前数是第一个减数,第二个减数一定在后面,所以,如果不在里面,则将该数放入HashMap中;如果在里面,则找到两数。

循环一遍即可找到结果,另外HashMap中查找的时间复杂度为O(1),遍历数组的时间复杂度为O(n),所以总体的时间复杂度为O(n)。

代码如下所示:

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
28
29
30
31
32
33
34
35
36
37
public class Solution_0001 {

public static int[] twoSum(int[] nums, int target){

Map<Integer, Integer> map = new HashMap<>();
int[] result = new int[2];
for(int index=0; index < nums.length ; index++){
// 计算差值
int temp = target - nums[index];

// 判断差值是否在HashMap中,有的话,则找到结果;没有的话,则加入到HashMap中。
if(map.containsKey(temp)){
result[0] = map.get(temp);
result[1] = index;
} else{
map.put(nums[index], index);
}
}
return result;
}

public static void main(String[] args) {
// int[] nums = {2,7,11,15};
// int target = 9;

// int[] nums = {3,2,4};
// int target = 6;
int[] nums = {3,3};
int target = 6;

int[] results = twoSum(nums, target);

for(int item: results){
System.out.print(item + " ");
}
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录