【leetcode初级】9-两数之和

• 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
  你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

• 思路：
  这是一道很经典的题目，我也是请教了其他同学才想出一个巧妙的办法，但也不是最快的。
  最直接的思路当然是O(n*n)这种两次循环遍历暴力查找了，这样做太慢了直接OUT。
  想到排序，当数组排好序后，怎么去找为目标值的两数之和呢。这个思路其实想一想就能明白。设置头尾两个指针，他们的和如果等于target最好，如果小于的话，将头指针后移。如果大于就尾指针前移，直到即将交叉那个时刻break掉。
  这时我们找到了那两个数值，但是题目要求是返回他们的Index，所以得保留原数组的下标。我一开始的时候用nums.index()这个函数去返回两个值的坐标，但是如果两个值是相等的话，这个函数只会返回第一个坐标。所以这里要用到python里的enumerate函数去生成一个index和value的索引去查。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums_copy = []
        for i in nums:
            nums_copy.append(i)
        nums.sort()
        i = 0
        j = len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                break
            elif nums[i] + nums[j] > target:
                j -= 1
            else:
                i += 1
        result = []
        for k,v in enumerate(nums_copy):
            if v == nums[i] or v==nums[j]:
                result.append(k)
        return result

• 刚才想先生成enum再去sort那个数组保证enum的值是原数组的顺序，但发现好像enum会随着sort后改变。这里需要进一步研究enumerate