LeetCode (01) Two Sums by Python

该博客记录自己刷LeetCode的过程，每道题AC后总结写博客，希望对自己又帮助。

目前刷题使用语言为Python。LeetCode链接。

问题描述如下。

image

首先我们分析题目。

题目的意思是给任意一个数组，在给一个目标数。在数组中找到两个数相加等于这个目标数，然后返回这两个数的下标。题目假设数组中只有唯一的两个数相加等于目标数，既返回的下标只有一组。

这道题属于很简单的题目，代码如下：

class Solution(object):

    def twoSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

        for i in range(len(nums)):

            others = target - nums[i]

            if others in nums:

                index1 = i

                index2 = nums.index(others)

                if index1 == index2:

                    continue

                else:

                    break

        return index1,index2

根据代码可以很明确的看到思路。我们遍历整个List。用 target 减去第 i 个数，得到others。然后在数组中找是否存在与others相等的数。如果存在，则返回 i 和 others的下标，如果不存在，则i + 1。

---

思路很简单，但是要避免一个小坑。
如果List是[3 , 3], target = 6。按照上述思路，nums[0] = 3 , others = 3, 然后在数组中找到与others相等的数后即退出循环，返回下标。我们返回的下标是[0, 0] 而实际正确的答案应该是[0, 1]。
出现这个原因是因为，我们在数组中找是否存在与others相等的数时，也包括了nums[i]，如果others 和 nums[i] 相等的情况，则会返回相同的下标。

---

解决这个小坑的方法有很多。
我的思路是返回的判断返回的下标,如果index1 = index2，那么这次循环不算，continue。然后进入下一次循环。
这样[3 , 3], target = 6 返回的下标是返回的下标是[1, 0]。
这个地方我感觉有点问题，应该是[0, 1]因为continue后i + 1了，所以会出这个问题。但是同样AC了。
解决这个小问题的思路很简单，这种情况只出现在others == nums[i]的情况，当我们判断这种情况出现时，我们把nums[i]的值置为无穷小，这样不会影响结果。
修改后的代码如下：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            others = target - nums[i]
            if others == nums[i]:
                nums[i] = -9999999
            if others in nums:
                index1 = i
                index2 = nums.index(others)
                if index1 == index2:
                    continue
                else:
                    break
        return index1,index2

image.png

很简单的AC了，用时有点暴力。
以上就是本题的解题代码和思路。很简单的题目，如果对这种方法不满意，也欢迎和我讨论新的方法。

---

补充：
去做LeetCode的题目是为了提高自己的算法水平和代码能力，基础薄弱。有的题目虽然自己的方法可以AC，但是有更好的方法可以学习。个人认为刷题不仅是为了AC，更多的是学习新的方法和技巧。
关于本题参考了其他博客，用Python Dict的方法用时更短也更巧妙。参考博客链接：http://www.cnblogs.com/zuoyuan/p/3698966.html

附上新的方法的代码：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dictTmp = {}
        for i in range(len(nums)):
            x = nums[i]
            if target - x in dictTmp:
                return (dictTmp[target-x], i)
            dictTmp[x] = i 

新的方法采用的是Python字典的方法。
我们首先把nums[i]的值对应的下标放在字典里。在遍历整个nums[i]时，判断target -
nums[i]是否在字典中，如果在字典中，则返回字典的下标，以及此时的i。
这种方法很巧妙，需要注意判断的位置。
由于表述问题可能不是很清楚，建议有疑惑的同学自己用笔亲自画一画或者Debug单步调试。
以上，祝好！