LeetCode_1. 两数之和

题目

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

思路

1. 暴力破解

• 思路分析

本质上，就是先取一个数 num ，然后判断 target-num 这个数在剩下的数中是否存在。
需要避免重复的比较：当取第一个数的时候，需要与剩下的所有数进行比较，之后取第二个数，则不需要再和第一个数相比，此时可以认为第一个数的比较工作已经结束了。

• 代码实现

  class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length=len(nums)
        for i in range(length):
            for j in range(i+1,length):
                if nums[i]+nums[j]==target:
                    return [i,j]

• 时间和空间消耗

结果表明，其实还好，没有想到暴力破解还能击败50%以上的用户。

2. 使用字典

• 思路分析

注意到使用字典的思路，是逐步扩充所谓“剩下的数”这个集合，其本质上和暴力破解的思路一致，只是顺序上是相反的，值得学习。

• 代码实现

  class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic={}
        for index,num in enumerate(nums):
            if dic.get(target-num) is not None:
                return [index,dic.get(target-num)]
            dic[num]=index

• 时间和空间消耗

小白 Python 几种解

LeetCode_167.两数之和 II

题目

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

思路

1. 暴力破解

• 思路分析

相比 LeetCode_1. 两数之和 而言，强调了升序排列，故而在 LeetCode_1. 两数之和 的暴力破解的方法基础之上，增加了一个条件语句，用于避免没有必要的搜索，具体的说，就是在 numbers 列表中迭代到比 target-num 还要大的数时，直接 break，具体见代码实现。

• 代码实现

  class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        length=len(numbers)
        for index,num in enumerate(numbers):
            for j in range(index+1,length):
                t=target-num
                if numbers[j]>t:
                    break
                if numbers[j]==t:
                    return [index+1,j+1]

• 时间和空间消耗

时间和空间的消耗都太大了…程序的效率不是很高。

2. 使用双指针

• 解题思路

两数之和 II - 输入有序数组 - 双指针 O(N) 时间复杂度 # 上面已经说的很完美易懂了。
认识到了，如果在有序的列表中，可以考虑双指针来解决问题。
认识到了，一个大佬 cyc 。

• 代码实现

  class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        length=len(numbers)
        i=0
        j=length-1
        while i<j:
            if target<numbers[i]+numbers[j]:
                j=j-1
            elif target>numbers[i]+numbers[j]:
                i=i+1
            else:
                return [i+1,j+1]

  注意：从概率上来讲，数组的首尾两个值的和刚好等于 target 的概率远低于不等于的情况，所以将 == 的情况放到else里效率应该会更高。

• 时间和空间消耗

比暴力破解法稍有提升。