一、题目
没事上leetcode上刷题。第一道两数之和,看似简单,实则没有想象中的简单。先看下题目:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数的下标。示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
二、代码实现
1、找出对应值
nums = [2, 7, 11, 15] target = 9 l = [] for x in nums: for y in nums: if (x + y) == target: #print x,y l.append(x) l.append(y) print list(set(l))
根据示例要求,通过上面的代码测试,发现和需求不一致,题目是打印下标,这里是找出了对应的值,未打印出下标。
2、打印下标
nums = [3,2,4] target = 6 n = range(len(nums)) l = [] for x in n: for y in n: # [3,3] 6 #if nums[x] != nums[y]: if x != y: if nums[x] + nums[y] == target: print x,y l.append(x) l.append(y) print list(set(l))
初始使用target=9 的数据测试时发现可以满足示例需求,修改为平台提交的函数格式后,在平台上提交后。发现其会换用输入值,发现在值为如下时不通过:
nums = [3,2,4] target = 6
这时候如果使用上面的代码,三个标值全会打印出来。因为3+3=6 。这时候增加了if x != y:条件,但平台上又测试了输入为nums = [3,3] target=6情况时又不满足需求。
3、暴力推导
再次修改代码,这次暴力点,先把所有的组合给搞出来。再通过推导式求出下标就OK了。代码如下:
from itertools import combinations nums = [2, 7, 11, 15] l = [c for c in combinations(nums, 2)] n = [ x for x in l if sum(x)==9] m = [ x for x in range(len(nums)) if nums[x]==n[0][0] or nums[x]==n[0][1] ] print m
这次的代码量非常少,看起来用的也非常高级,但在平台测试输入值为大的nums时,提示超出内存限制。因为使用了combinations方法,这个方法有点类似于笛卡尔积,消耗内存是一定的。
4、最终实现
这次换个思路,由加法换用减法。并通过字典方法,将满足条件的值和下标存入一个空字典中,并在满足条件后,取出vaule值,如下是最终提交给平台的代码:
#!/usr/bin/env python # coding=utf8 # =============================================================================== # Copyright (C) 2018 www.361way.com site All rights reserved. # # Filename :01sum.py # Author :yangbk <itybku@139.com> # Create Time :2018-08-16 14:33 # Description : # =============================================================================== class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ d = {} for i in range(len(nums)): #y = target - nums[x] x = nums[i] if target-x in d: return [d[target-x],i] d[x] = i
最终推导思路和各步实现代码,我已上传到我的github上:https://github.com/361way/python/blob/master/leetcode/01sum.py