原创

LeetCode-1.两数之和


1、两数之和

[TOC]

题目描述

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

  • 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

  • 示例:

    给定 nums = [2, 7, 11, 15], target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
    

解题思路

1、解法一:暴力解决(简单易懂)
  • 分析:

    • 循环数据,直到找到满足指定和为止。
  • 代码实现

    /**
      * @Description: 解法一:暴力解决
      * @param nums   给定数组
      * @param target 目标和
      * @return: void
      * @auther: xianzilei
      **/
    public static int[] twoSumSolutionOne(int[] nums, int target) {
        //定义初始结果,默认为[-1,-1]
        int[] result = {-1, -1};
        //从第一个要素循环查找
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                //如果满足结果,则直接结束程序,返回结果
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
    
  • 复杂度分析

    • 时间复杂度:
      • 最坏情况下循环次数为(n-1)+(n-2)+...+1=n*(n-1)/2,故时间复杂度为O(n^2)
    • 空间复杂度:
      • 未开辟新的空间,故空间复杂度为O(1)
2、解法二:两次遍历map法
  • 分析:

    • 鉴于暴力解决法中查找元素耗费时间为O(n),故考虑使用hash查找方式,将查找元素的时间复杂度降低为近似O(1);
    • 首先将数值的元素信息存储在map中,其中元素值为key,元素在数值中的索引为value,如果有相同值,则覆盖。
    • 遍历数值中的每一个要素,每次以指定和与该要素的差去查找是否存在对应的key,且索引值与当前遍历的数值的索引值不同,如果存在即返回结果,否则继续查找。
  • 代码实现

    /**
      * @Description: 解法二:两次遍历HashMap
      * @param nums   给定数组
      * @param target 目标和
      * @return: void
      * @auther: xianzilei
      **/
    public static int[] twoSumSolutionTwo(int[] nums, int target) {
        //定义初始结果,默认为[-1,-1]
        int[] result = {-1, -1};
        //使用hashMap,使用查询元素的复杂度由原来的O(n)降低为近似O(1)
        HashMap<Integer, Integer> map = new HashMap<>();
        //先将数据元素入map,其中key为元素值,value为索引位置
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        //遍历数组元素
        for (int i = 0; i < nums.length; i++) {
            //先求出目标和与当前元素的差
            int targetNum = target - nums[i];
            //利用差去map中查找是否存在对应的key,如果存在且二者的索引位置不同,则返回结果
            if (map.containsKey(targetNum) && i != map.get(targetNum)) {
                result[0] = i;
                result[1] = map.get(targetNum);
                break;
            }
        }
        return result;
    }
    
  • 复杂度分析

    • 时间复杂度:
      • 最坏情况下遍历两次完整的map,故时间复杂度为O(n)
    • 空间复杂度:
      • 由于定义一个hashMap,故空间复杂度为O(n)
3、解法三:一次遍历map法(最优)
  • 分析:

    • 解法二至少需要遍历两次map,如果n过大则会导致复杂度过高;
    • 故考虑在将元素put到map前做判断,以指定和与遍历到要素的差去查找是否存在对应的key,且索引不同,如果找到则返回结果,否则将元素入map(方式同解法二);
    • 可以将复杂度降低为解法二的一半;
  • 代码实现

    /**
      * @Description: 解法三:一次遍历hashMap(最优)
      * @param nums   给定数组
      * @param target 目标和
      * @return: int[]
      * @auther: xianzilei
      **/
    public static int[] twoSumSolutionThree(int[] nums, int target) {
        //定义初始结果,默认为[-1,-1]
        int[] result = {-1, -1};
        //使用hashMap
        HashMap<Integer, Integer> map = new HashMap<>();
        //遍历数组元素
        for (int i = 0; i < nums.length; i++) {
            //先求出目标和与当前元素的差
            int targetNum = target - nums[i];
            //利用差去map中查找是否存在对应的key,如果存在且二者的索引位置不同,则返回结果
            if (map.containsKey(targetNum) && i != map.get(targetNum)) {
                result[0] = map.get(targetNum);
                result[1] = i;
                break;
            }
            //否则将数据元素入map,其中key为元素值,value为索引位置
            else {
                map.put(nums[i], i);
            }
        }
        return result;
    }
    
  • 复杂度同解法二

Java
算法
  • 作者:贤子磊(联系作者)
  • 发表时间:2019-11-28 20:45
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 公众号转载:请在文末添加作者公众号二维码
  • 评论