0%

leetcode之旅-01-两数之和

Posted on Edited on In

1. 题目描述

题目描述

  • 概括：已知数组A和目标值T，在A中找到两个和为T的两个值。输出两个值的下标
  • 前提：数组中一定有解且有唯一解，不能重复利用数组元素。

2. 我的解法

暴力解法 ：双重循环，遍历数组nums，直到找到两个和为target的值，输出下标

1
class Solution {
2
    public int[] twoSum(int[] nums, int target) {
3
        for(int i=0;i<nums.length;i++)
4
            for(int j=i+1;j<nums.length;j++)
5
                if(nums[i]+nums[j]==target)
6
                {
7
                    return new int[]{i,j};//快速建立数组方法
8
                }
9
        return new int[]{0,0};//若没找到，就随便输出两个值，应该不可能有这种情况
10
        }
11
            
12
    }
  • 时间复杂度：O（ ）
  • 空间复杂度： O（1）

3. 解法二

充分利用hash table ：

  • 原解法：在我的解法的第二层循环主要是为了找到一个值，使两值相加为target。这个值可以理解为sub = target - nums[i]。第二层循环的时间复杂度为O(n)。

  • 新解法：利用哈希表可以避免循环，直接找到列表中某个值的特性，把数组的每个元素保存为 hash 的 key，下标保存为 hash 的 value ，这样只需判断 sub 在不在 hash 的 key 里就可以了。可使第二层时间复杂度将为O(1)。

    注意需判断哈希表找到的值是否和第一重循环找到的值相同，即 i = j

    1
    public int[] twoSum(int[] nums, int target) {
    2
      	//建立hash table
    3
        Map<Integer,Integer> map=new HashMap<>();
    4
        for(int i=0;i<nums.length;i++){
    5
            map.put(nums[i],i);
    6
        }
    7
      	//只需一重循环便可找到两个值
    8
        for(int i=0;i<nums.length;i++){
    9
            int sub=target-nums[i];
    10
          	//需判断找到的值是否是i
    11
            if(map.containsKey(sub)&&map.get(sub)!=i){
    12
                return new int[]{i,map.get(sub)};
    13
            }
    14
        }
    15
        throw new IllegalArgumentException("No two sum solution");
    16
    }
  • 时间复杂度：O(n)
  • 空间复杂度： O(n) 空间换时间

3. 解法三

算法二的简化版 ：不需要判断hash找到的值是否与第一个值相同。复杂度不变。相当于在一重循环中，不断往前找hash值

1
public int[] twoSum(int[] nums, int target) {
2
    Map<Integer,Integer> map=new HashMap<>();//hash无需提前加入
3
    for(int i=0;i<nums.length;i++){
4
        int sub=target-nums[i];
5
        if(map.containsKey(sub)){
6
            return new int[]{i,map.get(sub)};
7
        }
8
        map.put(nums[i], i);//无需判断重复，因判断时当前值还没加入
9
    }
10
    throw new IllegalArgumentException("No two sum solution");
11
}

总结

hash table 的利用，在一维列表中减少时间复杂度，直接查找某个值非常方便

扩展

HashMap

利用如下代码创建hashmap，自动根据建立相应key值的hash值。

1
Map<Integer,Integer> map=new HashMap<>()
2
map.put(nums[i],i)
3
//通过key值查找列表位置，隐藏了key值转换hash值，及hash对应的过程
4
map.containsKey(sub)//判断是否含有key值
5
map.get(sub)//去除该key值的索引号（下标）

hashmap的使用还待之后进一步总结

参考列表

  1. leetcode-两数之和
  2. 解决方案-wang
  3. 扩展-深入浅出学Java——HashMap