[Leetcode] Two Sum @Python

浏览数：57 / 时间：2015年06月08日

首先作这个题，最直接的思路是两个for循环，然而所带来的缺陷是时间复杂度太高O(n²)。所以要转变思路：如何能一次遍历就解决问题？

因为是两个数相加来得到一个既定的数（target），那就有一个思路是：能不能两头相加，然后通过头指针和尾指针来回向中间靠拢来实现？

答案是可以的。分两步走：

排序
设置头、尾两指针，实现一次遍历。

注意事项：

找到两个数后需要返回两个数的位置，所以需要先备份原序列，使用备份序列进行排序和查找操作，然后查看备份序列找到的数在原序列的位置。
在查看备份序列找到的数在原序列位置时，因为要找两个数，所以第一个数要从前遍历，第二个数要从后遍历。否则会出现如下错误：num = {0,2,4,0} target = 0

语法细节：

对于序列的复制，可以采用num[:]实现，效果是生成了一个与num相同的新的序列
对于Python一个类中方法的定义，第一个参数为self,
一个Python模块自己测试，使用 if __name__ == ‘__main__‘:
对于一个类Solution，创建实例方式:solution = Solution()

代码实现：

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        numtosort = num[:]
        numtosort.sort()
        i = 0 
        j = self.search(numtosort,target)
        while(i < j):
            if(numtosort[i] + numtosort[j] == target):
                be = self.before_search(num,numtosort,i)
                af = self.after_search(num,numtosort,j)
                if be < af:
                    return (be,af)
                else:
                    return (af,be)
            elif(numtosort[i] + numtosort[j] < target):
                i = i + 1
            else:
                j = j - 1
    def search(self,numtosort,target):
        for i in range(0,len(numtosort)):
            if numtosort[len(numtosort)-i-1] <= target:
                if i == 0:
                    return len(numtosort)-1
                else:
                    return len(numtosort)-i                            
    def before_search(self,num,numtosort,number):
        for i in range(0,len(num)):
            if(num[i] == numtosort[number]):
                return i+1
    def after_search(self,num,numtosort,number):
        for i in range(0,len(num)):
            if(num[len(num)-i-1] == numtosort[number]):
                return len(num)-i
if __name__ == ‘__main__‘:
    num = [-3,4,3,90]
    target = 0
    solution = Solution()
    print solution.twoSum(num,target)