首页 > 代码库 > [leetcode]Two Sum @ Python

[leetcode]Two Sum @ Python

原题地址:http://oj.leetcode.com/problems/two-sum/

题意:找出数组numbers中的两个数,它们的和为给定的一个数target,并返回这两个数的索引,注意这里的索引不是数组下标,而是数组下标加1。比如numbers={2,7,11,17}; target=9。那么返回一个元组(1,2)。这道题不需要去重,对于每一个target输入,只有一组解,索引要按照大小顺序排列。

解题思路:1,由于要找到符合题意的数组元素的下标,所以先要将原来的数组深拷贝一份,然后排序。

       2,然后在排序后的数组中找两个数使它们相加为target。这个思路比较明显:使用两个指针,一个指向头,一个指向尾,两个指针向中间移动并检查两个指针指向的数的和是否为target。如果找到了这两个数,再将这两个数在原数组中的位置找出来就可以了。

     3,要注意的一点是:在原来数组中找下标时,需要一个从头找,一个从尾找,要不无法通过。如这个例子:numbers=[0,1,2,0]; target=0。如果都从头开始找,就会有问题。

代码:

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        index = []
        numtosort = num[:]; numtosort.sort()
        i = 0; j = len(numtosort) - 1
        while i < j:
            if numtosort[i] + numtosort[j] == target:
                for k in range(0,len(num)):
                    if num[k] == numtosort[i]:
                        index.append(k)
                        break
                for k in range(len(num)-1,-1,-1):
                    if num[k] == numtosort[j]:
                        index.append(k)
                        break
                index.sort()
                break
            elif numtosort[i] + numtosort[j] < target:
                i = i + 1
            elif numtosort[i] + numtosort[j] > target:
                j = j - 1

        return (index[0]+1,index[1]+1)