专栏首页程序员周同学【LeetCode算法】两数之和

【LeetCode算法】两数之和

微信公众号:程序员周同学 关注可了解更多的教程及编程技巧。问题或建议,请公众号后台留言; 如果你觉得对你有帮助,欢迎点赞

内容目录

LeetCode第一题:两数之和题目描述题目分析题目解答思路一:双重for循环(1)代码(2)提交结果思路二:hashmap键值对一次遍历(1)代码(2)提交结果思考总结

LeetCode第一题:两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例:

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

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

题目分析

这一题我想大部分人第一思路应该都是双重for循环来遍历数组。这也是我的第一思路,遍历两次数组,当外循环下标和内循环下标对应的两个数相加为target时,退出循环。这时候我们就找出了这两个数,但我们需要考虑到题目条件不能重复利用数组中同样的元素。 其实我看到这个条件的时候想了半天, 这个条件的意思是:两个数据的值不能相同

例如:nums =[1,2,2,3] target = 4 只能返回 [0,3] 而不是 [1,2]

还是:两个数据的下标不能相同

例如:nums =[1,2,3] target = 4 只能返回 [0,2] 而不是 [1,1]

又或者两者都有(好像有点钻牛角尖)

题目解答

思路一:双重for循环

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

(1)代码
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        for (int i = ; i < length; i++) {
            for (int j = ; j < length; j++) {
                //这里把条件当做不能使用相同的下标元素
                if (j != i && nums[i]+nums[j] == target)
                    return new int[]{i,j};
            }
        }
        return new int[]{};
    }
}
(2)提交结果

思路一代码提交结果

思路二:hashmap键值对一次遍历

将nums[i]作为key,i作为value。 hashmap搜索算法时间复杂度为O(1) 整个算法在最坏的情况下将数组nums中所有值遍历完也就是O(n) 所以这种解法的时间复杂度:O(n)

(1)代码
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        HashMap<Integer,Integer> hashMap = new HashMap();
        for (int i = ; i < length; i++)
            //如果hashmap中有这个key则直接返回
            //如果没有,则存入hashmap之中
            if (hashMap.containsKey(target - nums[i]))
                return new int[]{i,hashMap.get(target-nums[i])};
            else
                hashMap.put(nums[i],i);
        return new int[]{};
    }
}
(2)提交结果

思路二代码提交结果

思考总结

根据这题的两种解法就可以看出,不同的算法会有不同的效率,所以我们在编程的时候,不要仅仅局限于解出这个题目,而是要在解决问题的基础上想办法去优化你的算法,使之效率更高。 LeetCode算法题不能停~

本文分享自微信公众号 - 程序员周同学(jay-ztx),作者:周同学c

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-17

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【数据结构】线性表的顺序储存结构

    1.写在前面1.C语言关键词---typedef3.线性表的特点4.线性表的顺序表示5.线性表的顺序表示(顺序表)结构

    程序员周同学
  • 【数据结构】线性表的顺序表示

    1.写在前面1.C语言关键词---typedef3.线性表的特点4.线性表的顺序表示5.线性表的顺序表示(顺序表)结构

    程序员周同学
  • 【巩固学习_实训】第一次任务

    1-2: 十进制整数转二进制(5分) 样例输入:267 样例输出:100001011

    程序员周同学
  • 算法细节系列(21):贪心有理?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode41|数组中数组出现的次数

    请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

    后端Coder
  • LeetCode49|搜索旋转排序数组

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    后端Coder
  • 【LeetCode】1.两数之和

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

    Delevin
  • 动态规划设计

    输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

    黑白格
  • LeetCode第七天

    ==数组 Medium== 40.(162)Find Peak Element ? JAVA //斜率思想,二分法 class Solution { p...

    郭耀华
  • 每日算法系列【LeetCode 312】戳气球

    有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

    godweiyang

扫码关注云+社区

领取腾讯云代金券