资讯专栏INFORMATION COLUMN

LeetCode-1 Two Sum

Dr_Noooo / 2061人阅读

摘要:题目解析给出一列整数数组和一个数字,如果计算出数组中的两个数之和等于,那么返回数组两个数的索引。解答基础的解法应该是将数组遍历之后取和,如果和等于那么结束循环。这种解法的效率为。

题目

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:

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

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

解析

给出一列整数数组和一个数字target,如果计算出数组中的两个数之和等于target,那么返回数组两个数的索引。

解答

基础的解法应该是将数组遍历之后取和,如果和等于target那么结束循环。这种解法的效率为O(n^2)。

    public int[] twoSum(int[] nums, int target) {
        int i,j;
        // 双层循环取和
        for(i=0;i

更高效的解法可以通过将结果放入HashMap中,通过HashMap的containsKey的方法来查找答案。
相比于O(n)效率的数组循环,containsKey方法如果在计算hash值能立马找到key那么效率为O(1),如果找不到key需要继续查找链表的话,那么效率为O(n),但是又因为HashMap的hash值是分散的,所以查找链表的长度相比于数组循环的长度是更少的,所以总的来说HashMap的效率是更好的。

    public static int[] twoSum3(int[] nums , int target){
        Map map = new HashMap<>();
        for(int i =0;i           
               
                                           
                       
                 

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/72530.html

相关文章

  • Leetcode 1: Two Sum 加和

    摘要:难度就是说给一个整数数组如给一个目标数字如从数组中找出相加为这个目标数字的两个数的下标就返回的下标只需要给出满足条件的一对数字即可这个题想起来比较直接此处给出两种解法这之后的题目中还有多个数字相加的相对较难的题目第一种将数组排序以两个游标 Two Sum Given an array of integers, return indices of the two numbers suc...

    PascalXie 评论0 收藏0
  • leetcode 1 Two Sum Java & JavaScript解法

    摘要:返回这两个元素的位置。每个输入都有且仅有一组满足条件的元素。想法如果使用蛮力法可以简单的解决这个问题。但是需要两层循环,效率低。用来存储,每一个元素和目标元素的差值和这个元素的位置。因为里的对象也是键值对。 题目详情 Given an array of integers, return indices of the two numbers such that they add up t...

    Guakin_Huang 评论0 收藏0
  • leetcode 1 Two Sum Java & JavaScript解法

    摘要:返回这两个元素的位置。每个输入都有且仅有一组满足条件的元素。想法如果使用蛮力法可以简单的解决这个问题。但是需要两层循环,效率低。用来存储,每一个元素和目标元素的差值和这个元素的位置。因为里的对象也是键值对。 题目详情 Given an array of integers, return indices of the two numbers such that they add up t...

    chanjarster 评论0 收藏0
  • LeetCode.1 两数之和(Two Sum)(JS)

    摘要:开坑,以后每周刷一两道一题目两数之和给定一个整数数组和一个目标值,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。但是,你不能重复利用这个数组中同样的元素。 开坑,以后每周刷一两道LeetCode 一、题目 两数之和: 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应...

    Gu_Yan 评论0 收藏0
  • Leetcode 1:两数之和

    摘要:给定一个整数数组和一个目标值,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。示例给定因为所以返回方法,暴力解法。函数可以将一个数组转化为一个从开始,值为数组对应元素的字典。 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中...

    Taste 评论0 收藏0

发表评论

0条评论

Dr_Noooo

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<