大家好,又见面了,我是你们的朋友全栈君。
题目描述
链接: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账号...