LeetCode1_两数之和

2019-09-08

用python语言解答LeetCode的1题

碎碎念（不用看！最后一句话和下一节开始才是重点~~~）

自己第一眼思路：

顺序遍历咯，，，但是感觉很麻烦的亚子，

换个思路：

Step1.先把给定的数组进行排序，因为人家题目中只说了给定一个整数数组，没说是顺序排列好的数组。
Step2.来两个指针（是不是叫指针，我忘了，反正就是两个遍历数组的变量），一个放在开头，一个放在结尾，就把他俩叫start和end吧，.
Step3. 先考虑特殊情况，
nums[start]和target比较，如果nums[start]大于等于target，返回None；
nums[start]和target比较，如果nums[end]小于等于target，返回None。
想一想还有什么特殊情况没，，，没想到，后面有了再来加。
Step4，特殊情况处理完了就可以正常处理了。我们让start先别动，end先走，nums[end]大于target的话就一直end–，直到nums[end]小于等于target，若等于，则先判断nums[start]是否等于0，如果不等于，继续end–，然后判断sum = nums[end]+nums[start]


    if sum == target:
         return start, end
    elif sum > target:
        end -= 1
    else :
        start += 1

这样好像解不出来，，，因为举个栗子：
nums = [2,3,5,8,9,11],target = 6
应该返回none，但是上述思路里面没有提到这种情况，智商有限，，，打算去看大神们的思路了。。。

市面上的思路有两种，第一种是暴力破解法，第二种是哈希表处理

方法一：暴力破解法

思路简单粗暴，进行两次for循环遍历数组，查找出符合要求的元素。

有两点需要注意，其实是我这个小白踩得坑。

第一点，i是从0开始的，而j是从i+1开始的，因为题目中明确规定了你不能重复利用这个数组中同样的元素。

如果j也是从0开始，那么试想一下，如果nums=[2,3,3,5,6],target=4的情况，返回值会是[0,0],而题目已经表明不接受这种答案，如果j是从i+1开始，那么这个例子的返回值会是None

第二点，我在if后面又跟了一个else：return None，然后测试的时候发现所有的例子返回值都是None。一脸懵逼，，，，直到自己删了一下else试了一下，发现返回值正确了。这个原因，感觉不需要解释，如果有人不明白评论留言，我再加解释。。。

方法一代码如下：


    #coding:utf-8

    class Solution():
        def twoSum(self, nums, target):
            """

            :param nums: List[int]
            :param target: int
            :return: 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


    if __name__ == '__main__':
        nums = [2, 11, 7, 8]
        target = 4
        test = Solution()
        print(test.twoSum(nums, target))

方法一的运行结果如下

avatar

暴力穷举法确实没毛病，但是嘞，超出时间限制啦，，，所以还是得学一种有技术含量的解法啦—哈希表处理

方法二：哈希表处理

思路呢就是使用一个哈希表来存储已经访问过的整数（这里通过字典来模拟哈希表），从左往右依次遍历整个数组并用target减去当前遍历的数组元素，然后在哈希表中查找这个差值，如果找到这个差值，则直接返回它的下标以及当前遍历元素的下标，如果未找到就将这个数组元素存储到哈希表中，直到找出符合要求的两个元素，否则返回None。

不知道解释清楚了木有，举个栗子吧.

假设数组nums = [2, 11， 7， 15],target = 9

avatar

Step1:一开始从左往右依次遍历整个数组，遍历到2的时候我们用9-2=7，也就是说，要查找的目标值是7，查找发现在哈希表中没有存储7这个元素，

avatar

此时我们把2放到哈希表里面去，以及它的索引0也放到哈希表里面去

avatar

Step2.然后再遍历，遍历到11的时候，用9 - 11 = -2，此时，目标值为-2，看-2在哈希表中是否可以查找到，发现哈希表中找不到该目标值，

avatar

那么还是把当前遍历元素11以及其索引值1放入哈希表中。

avatar

Step3.接着往右遍历，当遍历到7的时候，我们会发现9-7=2,2存在于哈希表中，所以此时，我们返回2的索引值0，同时返回当前遍历值7的索引值2，最终返回值为[0, 2],问题解决~~~

avatar

方法二代码


    #coding
    # 该程序用哈希处理表解决LeetCode1两数之和问题。


    class Solution():
        def twoSum(self, nums, target):
            """

            :param nums: List[int]
            :param target: int
            :return: List[int]
            """

            dict = {}

            length = len(nums)
            for x in range(length):
                complement = target - nums[x]
                if complement in dict:
                    return [dict[complement], x]
                else:
                    dict[nums[x]] = x


    if __name__ == '__main__':
        nums = [3, 7, 5, 2, 8, 10]
        target = 9
        test = Solution()
        print(test.twoSum(nums, target))

方法二的运行结果

avatar

Reference：

1.https://www.bilibili.com/video/av51296602?from=search&seid=6257983938624651018