文章目录
  1. 1. Two sum
    1. 1.1. 演练
    2. 1.2. 优化
      1. 1.2.1. 桶装法
      2. 1.2.2. HashMap的解法

从今天开始我要坚持刷leetCode,就是要让自己坚持一种学习的状态,当然了,给自己定的目前是一周至少20道,平均每天4道(星期天的话,我觉得没必要一定要刷,不过星期天实在没事,刷题比打游戏要更有意义吧)。

Two sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

演练

  1. 先审题
    输入:系列的数组,和一个target的结果
    输出: 从数组中能拿到两个数字之和等于这个target

  2. 第一反应

肯定是遍历,拿一个数字和后面的数字做求和,和target对比.这就需要我们两次遍历,第一次遍历去一个数字A,第2遍历是从剩下的数组遍历,和数字之和等于target,这个时间复杂度是$x^{2}$.

能有么?可以,比如哪些数字大于target直接排除,可是这个对于遍历对于最坏的结果是没有影响的,不过已经做到了局部优化。

能优化到时间复杂度为o(n)么?

答案是可以的?

优化

桶装法

这个方法有点二,大家应该记得桶排序,如对100以内的数字排序:

我们也可以为我们的数字,假如说是100以内的(只是假设,那么我们就可以,把相关数字,然后和target求差值,看下差值的桶里有没有。这样遍历只需要一次,但是空间开销很大。

不过若是数组中的不唯一,可能会让大家想到了散列表,也就想到了HashMap(有些语言中叫字典)

HashMap的解法

这个是将index和数值对方放到HashMap中,key就是我们的数字,value是索引值,这样是不是很好呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum(int[] arr, int target) {
if (arr == null || arr.length < 0 ) {
return new int[]{-1,-1};
}

Map<Integer, Integer> items = new HashMap<>();
for (int index = 0; index < arr.length; index++ ){
int key = arr[index];

if (items.get(target - key) != null ) {
return new int[]{index ,items.get(target - key)};
} else {
items.put( key, index);
}
}
return new int[]{-1,-1};
}
文章目录
  1. 1. Two sum
    1. 1.1. 演练
    2. 1.2. 优化
      1. 1.2.1. 桶装法
      2. 1.2.2. HashMap的解法