专栏首页木又AI帮【leetcode刷题】20T1-两数之和

【leetcode刷题】20T1-两数之和

木又同学leetcode刷题又回来了,今年按照题目顺序刷


木又同学2020年第1篇解题报告

leetcode第1题:两数之和

https://leetcode-cn.com/problems/two-sum/


【题目】

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

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

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

【思路】

拿到题目,我们自然能想到最直接的解法,暴力破解,两层循环,时间复杂度O(n ^ 2)。

我们也可以使用hash,遍历nums数组每个元素n,如果target-n存在于hash中,则找到这样两个数,返回其下标。有一个地方需要注意,有可能两个元素值相同,比如数组中存在两个3(target为6),需要单独处理。

【代码】

python版本

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 特殊情况
        half = target // 2
        if nums.count(half) == 2 and half * 2 == target:
            return [nums.index(half), len(nums) - 1 - nums[::-1].index(half)]

        # hash
        d = {}
        for i, n in enumerate(nums):
            d[n] = i

        # 遍历
        for i, n in enumerate(nums):
            if n == target - n:
                continue
            if (target - n) in d:
                return [i, d[target - n]]

C++版本

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 暴力
        vector<int> res;
        for (int i=0; i<nums.size(); i++){
            for (int j=i+1; j<nums.size(); j++){
                if (nums[i] + nums[j] == target){
                    res.push_back(i);
                    res.push_back(j);
                }
            }
        }
        return res;
    }
};

历史文章:T1-Two Sum

给我好看

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

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

原始发表时间:2020-01-10

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T165-最长上升子序列

    https://leetcode-cn.com/problems/longest-increasing-subsequence/

    木又AI帮
  • 【leetcode刷题】T9-寻找旋转排序数组中的最小值

    今天分享leetcode第9篇文章,也是leetcode第153题—寻找旋转排序数组中的最小值,地址是:https://leetcode.com/problem...

    木又AI帮
  • 【leetcode刷题】T7-Search Insert Position(搜索插入位置)

    今天分享leetcode第7篇文章,也是leetcode第35题—Search Insert Position,地址是:https://leetcode.com...

    木又AI帮
  • Leetcode Solutions(一) two-sum

    在map[整数]整数的序号中,可以查询到a的序号。这样就不用嵌套两个for循环了。

    小歪
  • Leetcode-Solutions 1.two-sum (Python&Golang)

    恩,最后找队友一起刷题。喜欢可以联系我 ,来公众号“Python爬虫与算法进阶”找我哦

    小歪
  • 剑指Offer LeetCode 面试题53 - I. 在排序数组中查找数字 I

    输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2:

    TrueDei
  • Leetcode#1.Two Sum(两数之和)

    题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums ...

    武培轩
  • LeetCode68|和为s的两个数字

    双指针的使用,最近一段时间的输出文章都是自己之前做过的内容,自己打算将做过的题都整理成一篇篇文章进行梳理一下,喜欢看java的文章可以查看历史记录,本人写过My...

    后端Coder
  • Leetcode算法【34在排序数组中查找元素】

    在之前ARTS打卡中,我每次都把算法、英文文档、技巧都写在一个文章里,这样对我的帮助是挺大的,但是可能给读者来说,一下子有这么多的输入,还是需要长时间的消化。

    程序员小跃
  • 每日算法题——两数之和

    许久不见,终于开始在公司上班了,有一点不好的就是一整天都要戴着口罩,闷得慌,不知道大伙儿有没有这种感觉。

    用户2802329

扫码关注云+社区

领取腾讯云代金券