leetcode之 两数之和 题目解答C/python

leetcode之 两数之和 题目解答C/python题目描述链接: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]解答C语言:…

大家好,又见面了,我是你们的朋友全栈君。

题目描述

链接: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]

 

解答

C:

首先搞清楚函数中的形参的意思: int* nums表示传进去一个数组的地址; int numsSize表示传进去的数组大小; int target表示数组中两数相加需要等于的值; int* returnSize表示返回的数组的大小。

数组nums的index从0到numsSize-1,因此使用非常常见的双循环嵌套方法。i从0到numsSize-2, j从0到numsSize-1去遍历,一旦发现 nums[i]+nums[j] 和 target 相等,就保存i,j,输出结果。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *a = (int*)malloc(sizeof(int)*2);
    for(int i = 0; i <= numsSize-2; ++i) {
        for(int j = i+1; j <= numsSize-1; ++j) {
            if(nums[i]+nums[j] == target) {
                a[0] = i;
                a[1] = j;
                *returnSize = 2;
                return a;
            }
        }
    }
    *returnSize = 0;
    return 0;
}

执行结果:

通过

显示详情

执行用时:4 ms, 在所有 C 提交中击败了99.03%的用户

内存消耗:6 MB, 在所有 C 提交中击败了51.84%的用户

 

python

方法1:一个菜鸟的不计成本的方法。定义一个空字典full_dict,然后把nums列表里任意两项都做相加。相加之和值作为key ,两项以列表形式合并作为value。将nums所有项的遍历一遍后,就产生了涵盖所有和值得full_dict字典,取key为target的value即为本题答案。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        full_dict = {}
        dict_key = 0
        for i in range(0, len(nums)):
            for j in range(0, len(nums)):
                if j == i:
                    continue
                dict_key = nums[i]+nums[j]
                full_dict.update({dict_key:[j, i]})
        return full_dict[target]

 

执行结果:

超出时间限制

方法2:这个方法比方法1巧妙多了。定义了一个字典hashmap = {}用于由值来获取索引。对列表nums遍历,取出每一项索引和数值,计算可以与该值求和得到target的另外一个值的大小,并搜索是否在nums里,如果是则将符合条件的两个值得索引打印出来。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        print "step 1"
        for index, num in enumerate(nums):
            print "step 2 index:", index
            print "step 2 num:", num 
            another_num = target - num
            print  "step 3 another_num:",another_num
            if another_num in hashmap:
                return [hashmap[another_num], index]
            hashmap[num] = index
        return None

执行结果:

通过

显示详情

执行结果:

通过

显示详情

执行用时:8 ms, 在所有 Python 提交中击败了99.74%的用户

内存消耗:13 MB, 在所有 Python 提交中击败了89.92%的用户

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/138850.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号