专栏首页Java爬坑系列【LeetCode】两数之和

【LeetCode】两数之和

题目说明

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路1:穷举法

从题目意思理解,就是从给定的整数数组中找到两个整数,使得它们的和与给定的数相等。那最简单粗暴的方式就是枚举了,嗯,先来试试最简单的。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        return exhaustAlgorithm(nums,target);
    }
    // 穷举法
    private int[] exhaustAlgorithm(int[] nums, int target){
        int length = nums.length;
        int i = 0;
        int j = 1;
        while (nums[i] + nums[j] != target) {
            j++;
            if (j >= length){
                i++;
                if (i >= length - 1){
                    break;
                }
                j = i + 1;
            }
        }
        // 说明不存在这样的组合
        if (nums[i] + nums[j] != target) return null;
        int[] result = {i,j};
        return result;
    }
}

时间复杂度:\(O(n^2)\)

运行结果如下:

80ms,才击败了11.13%的用户,说明优化空间还很大。

解题思路2:倒推法

穷举法的效率一般都比较差,所以需要尝试一些新姿势。我们再来分析一下上面的穷举算法,要从一个集合中找出两个数,使得它们的和与给出的数target相等,使用穷举算法时,当我们选出第一个数a后,需要循环遍历之后的数,然后一一进行加和判断,但实际上,我们只需要知道剩下的数里,有没有数等于target - a即可,而每次从数组中找到某个数是否存在,都需要遍历一次,因此,更好的做法是将数与对应的序号存到一个map中,这样就能将查找效率从\(O(n)\)提高到\(O(1)\)。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        return mapSolution(nums,target);
    }
    // 倒推法
    private int[] mapSolution(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            map.put(nums[i],i);
        }

        for (int i = 0; i < nums.length; i++){
            int num = target - nums[i];
            // 判断num是否存在,如果已经存在,则直接返回
            if (map.get(num) != null){
                return new int[] { map.get(num), i};
            }
        }
        return null;
    }
}

这里我们对nums数组进行了两次遍历,第一次遍历是将所有元素都存入map中,第二次遍历是查找目标的整数对是否存在。

但再仔细想想,是否还能再优化呢?

答案是肯定的,在这个题中,要寻找的整数是成对存在的,所以我们可以只进行一次遍历。

如果target减去当前遍历数值后的数不存在于map中,则将当前数值与序号的映射关系存入map中。也许你会问,那找到第一个要寻找的数时,第二个数显然还不在map中,那怎么办呢?别着急,前面已经说过了,因为要寻找的数是成对存在的,这里我们假设为ab,所以遇到第一个数a时,由于b还没有存入map,所以先将a存入map中,我们在找到第二个数b后,此时a已经在map中了,所以就能在一次遍历中顺利找到了这对我们想要的整数了。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        return mapSolution(nums,target);
    }
    // 倒推法
    private int[] mapSolution(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            int num = target - nums[i];
            // 判断num是否存在,如果已经存在,则直接返回
            if (map.get(num) != null){
                return new int[] { map.get(num), i};
            }
            // 不存在则当前数值与序号的映射关系存入map中
            map.put(nums[i], i);
        }
        return null;
    }
}

时间复杂度:\(O(n)\)

空间复杂度:\(O(n)\)

运行结果如下:

一下降到了9ms,效率大大提升,击败85%的用户,嗯,看来效果确实很显著。

本题中文链接

本题英文链接

如果你有更好的想法,也欢迎留言交流讨论~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【动态规划】完全背包问题

    在上一篇中,我们对01背包问题进行了比较深入的研究,这一篇里,我们来聊聊另一个背包问题:完全背包。

    弗兰克的猫
  • 类的进化史

      类无疑是C++最重要的概念之一,是从C的面向过程到C++面向对象的重要转变的基础,下面我们就来谈谈C++中的类是怎样演变的。   先来看看C中的结构体(st...

    弗兰克的猫
  • 【动态规划】多重背包问题

    这个背包,听起来就很麻烦的样子。别慌,只要你理解了前面的两种背包问题,拿下多重背包简直小菜一碟。

    弗兰克的猫
  • 【LeetCode】两数之和

    Jacob丶
  • 查找数组中两数之和等于指定的数

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

    Melody132
  • 【LeetCode】136. Single Number

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】找出数组中重复的数字day01

    居士
  • 剑指Offer题解

    在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少存在一个数字是重复的。 请找出数组中任意一个重复的数字,但不能修改输入的数组。 例如输...

    星如月勿忘初心
  • 哈希表-LeetCode 217、219、220、232(hashset、hashmap)

    给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

    算法工程师之路
  • Largest Number Greater Than Twice of Others

    思路1: 非排序,如果存在一个数,比其他任何数的两倍还大必然是最大数。时间复杂度为O(n2)O(n^2)

    用户1147447

扫码关注云+社区

领取腾讯云代金券