001TwoSum

发表于 | 更新于: | 分类于 |

题目

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:

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

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

给一个数组，返回两个数的索引，这两个数之和得和目标数相等。

你可以需要假设每个输入只有确切的一个结果，并且你不可使用相同的元素两次

解题过程

v0.1

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in nums:
            for j in nums:
                if(nums[i] + nums[j] == target):
                    return[i, j]

这里其实想法是对的，但for i in nums这是对列表的每一项遍历，是值，不是索引

v0.2 只能找到第一对 

1
2
3
4
5
6
7
8
def twoSum(self, nums, target):  
   if nums:
       n = len(nums)
       length_list = list(range(0, n+1))
       for i in length_list[:(n-2)]:
           for j in length_list[(i+1):]:
               if(nums[i] + nums[j] == target):
                   return[i, j]

其实这里可以不用新建一个length_list列表，直接用range就行了。这里纠结只找到一对，是因为没有完全理解题意

v0.3 输出的是列表的列表，没有考虑异常情况 len(list) >=4 

1
2
3
4
5
6
7
8
9
if nums:
    n = len(nums)
    result = []
    length_list = list(range(0, n))
    for i in length_list[:(n-2)]: #这里我弄错了，切片操作不包括右边
        for j in length_list[(i+1):]:
            if(nums[i] + nums[j] == target):
                result.append([i,j])
return result

初稿，空列表是返回none，一个数或没有满足条件返回[ ]

v1.0 算法复杂度是O(n2) v1.0

1
2
3
4
5
6
7
8
9
if nums:
    n = len(nums)
    result = []
    length_list = list(range(0, n))
    for i in length_list[:(n-1)]:
        for j in length_list[(i+1):]:
            if(nums[i] + nums[j] == target):
                result.append([i,j])
    return result

  • 如何判断一个列表不为空

    • PEP8不推荐用，判断长度的方式

      从逻辑上讲，一个集合（列表也可以看做一个集合）是否为空是比集合元素个数更基本的性质。比如：自然数集合不为空，但是自然数集合的元素个数是不知道的

      从风格上讲，一个列表长度为0隐含了一个列表为空，但是Python的格言是explicit is better than implicit，你判断一个列表是否为空不需要用一个更强的性质“长度”为0来判断。同理，也更不需要用

      1
      2
      3
      4
      5
      > try:
      >    aList[0]
      > except:
      >    # empty!
      >

      来判断。虽然，这样也是可以的。但是你可以这样做不代表你应该这样做。Python不是Perl。

v1.1

1
2
3
4
5
6
7
8
9
if nums:
   i = 0
   j = 1
   if (i < len(nums)):
       if (j < len(nums)):
           if (nums[i] + nums[j] == target):
               return [i, j]
           j += 1
           i += 1

v1.2 超时

1
2
3
4
5
6
if nums:
   n = len(nums)
   for i in range(n-1):
       for j in range(i+1, n):
           if (nums[i] + nums[j] == target):
               return [i, j]

v1.3 索引可能会倒着

这里思路是用target - num[i]，然后再看看这个数在没在列表里

其实这个思路是对的，后面的最终答案也是这个思路

我没想到的是可以在新建的字典里操作，这里以及后面的版本，都是在原本的列表里操作，所以要考虑好多种情况

1
2
3
4
5
6
for i in range(n-1):
    other_num = target - nums[i]
	# 这里弄错了，是索引的范围，而other_num是值
    if (other_num >= 0 and other_num <= n-1 ):
        j = nums.index(other_num)
        return[i,j]

v1.4 [3,3] 6 不行

1
2
3
4
5
6
for i in range(n-1):
    other_num = target - nums[i]
    if other_num in nums:
        j = nums.index(other_num)
        if j != i:
        	return[i,j]

v1.5 [3,2,4] 6不行， [3],[3,3]ok

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if nums:
           n = len(nums)
           index = []
           for i in range(n-1):
               other_num = target - nums[i]
               if other_num in nums:
                   for item in enumerate(nums):
                       if item[1] == other_num:
                           index.append(item[0])
                   if other_num == nums[i]:
                       if len(index) > 1:
                           j = index[1]
                       else:
                           j = index[0]
                           print(j)
                       return [i,j]

v1.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if nums:
            n = len(nums)
            index = []
            for i in range(n- 1):
                other_num = target - nums[i]
                if other_num in nums:
                    if other_num == nums[i]:
                        for item in enumerate(nums):
                            if item[1] == other_num:
                                index.append(item[0])
                        if other_num == nums[i]:
                            if len(index) > 1:
                                j = index[1]
                            else:
                                j = index[0]
                                print(j)
                    else:
                         j = nums.index(other_num)
                   
                    return [i,j]

v1.7

UnboundLocalError: local variable ‘j’ referenced before assignment 3.2.4 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if nums:
    n = len(nums)
    num_index = []
    if n > 1:
        for i in range(n-1):
            other_num = target - nums[i]
            if other_num == nums[i]:
                print(nums.count(other_num))
                if nums.count(other_num) != 1:
                    for item in enumerate(nums):
                        if item[1] == other_num:
                            num_index.append(item[0])
                    j = num_index[1]                       
            else:
                if other_num in nums:
                   j = nums.index(other_num)
        return [i,j]

v1.8 借鉴java 循环下标 最后一测试用例不行 时间超时 python嵌套循环非常慢

1
2
3
4
5
6
7
8
if nums:
    n = len(nums)
    for i in range(n):
        for j in range(i+1,n):
            if (nums[i] + nums[j] == target):
                return[i, j]
          #  j += 1 这两个多余 
    	# i += 1

最终答案

v1.9 Runtime: 7201 ms 2.09%

对循环的优化所遵循的原则是尽量减少循环过程中的计算量，有多重循环的尽量将内层的计算提到上一层。

1
2
3
4
5
6
7
if nums:   # 这个可去掉，因为nums是空集合的话，遍历时直接返回空值
    n = len(nums)
    for i in range(n-1):
        temp =nums[i] # 循环之外能做的事不要放在循环内
        for j in range(i+1,n):
            if (temp + nums[j] == target):
                return[i, j]

v2.0 看了讨论后写的方案，但是有错误

修改错误后，提交 69ms，46.93%

1
2
3
4
5
6
7
dict = {}
for i in range(len(nums)):
           # dict = {} 不应该放在循环里，不然每次都会初始化空字典，覆盖点原来的数据
            if((target - nums[i]) in dict):
                return[dict[target - nums[i]], i]
            else:
                dict[nums[i]] = i

碰到的一些问题

  • 如何做到返回一个个列表，不采用列表的列表的集合

    • 有一个结果就打印一次

    • 但是在类中，好像无解，或者可以返回好多次？

      不能返回好多次，但可以返回多个值

  • markdown 表示平方 上标的方法

    • typora打开设置，勾选上标后，语法 “2 ^ n ^”
    • markdown用$符号包裹就可以实现latex行内公式，$km^2$实现
    • markdown
      • 用<sub>和</sub>包括下标文字：H2O
      • 用<sup>和</sup>包括上标文字：X2+2x+1 = 0

  • for i in 0 怎么理解

    A range object will be empty if r[0] does not meet the value constraint.

  • python 中条件表达式是 lazy evaluation 的，也就是说如果存在条件表达式 if x and y，在 x 为 false 的情况下 y 表达式的值将不再计算。因此可以利用该特性在一定程度上提高程序效率。

  • 字典为什么查找快，它是采取了什么原理，查找时没有遍历所有数据吗，不遍历，它怎么找到数据的

    为什么dict查找速度这么快？因为dict的实现原理和查字典是一样的。假设字典包含了1万个汉字，我们要查某一个字，一个办法是把字典从第一页往后翻，直到找到我们想要的字为止，这种方法就是在list中查找元素的方法，list越大，查找越慢。

    第二种方法是先在字典的索引表里（比如部首表）查这个字对应的页码，然后直接翻到该页，找到这个字。无论找哪个字，这种查找速度都非常快，不会随着字典大小的增加而变慢。

    dict可以用在需要高速查找的很多地方，在Python代码中几乎无处不在，正确使用dict非常重要，需要牢记的第一条就是dict的key必须是不可变对象。

    这是因为dict根据key来计算value的存储位置，如果每次计算相同的key得出的结果不同，那dict内部就完全混乱了。这个通过key计算位置的算法称为哈希算法（Hash）。

    by廖雪峰Python教程

    ​

  • 可以写下思路，流程图，再根据流程图写程序，不然脑袋里是一袋浆糊
  • 分析程序时，可以将值打印出来，debug模式单行运行已很好，可以知道程序的运行路线，看看和自己想的哪里不一样

总结

  • 一直在操作数据，而不是操作索引 —> 这里是列表还是不太熟悉

  • 思路所限，做的题还是比较少 —> 碰的多了就好了

  • 字典查找非常快，这个知道，但如何应用到程序却不会，这道题是个很好的例子

  • 判断一个列表不为空，推荐用if nums:而不推荐用判断列表长度不为0的形式

  • 写程序时要思路清晰，可以画流程图/结构图来帮助理解

  • 对循环的优化所遵循的原则是尽量减少循环过程中的计算量，有多重循环的尽量将内层的计算提到上一层。

  • 附上一个stackflow上的回答

    for(i=0;True;i++) in python?

    You could make use of itertools:

    1
    2
    3
    4
    5
    from itertools import takewhile, count

    # ...
    def myfunc():
        return takewhile(lambda x: x is not None, (lookup(i) for i in count(1)))

    If you don’t like takewhile for whatever reason:

    1
    2
    3
    4
    for i in count(1):
         res = lookup(i)
         if res is None: break
         yield res

如果下次碰到这个题目应该怎么思考

  1. 直接brute force, 怎么简单怎么来，就是看到这个第一反应
  2. 然后写出后，分析它的算法和空间复杂度
  3. 然后优化，查找类的可以用字典来代替（优化的套路应该是有限的，只不过自己现在刚起步，碰到少）
  4. 最后想想有没有别的思路，如正反思考