LintCode_chapter2_section9_two-s

# coding = utf-8
'''
Created on 2015年11月9日

@author: SphinxW
'''
# 给一个整数数组，找到两个数使得他们的和等于一个给定的数target。
#
# 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是1到n，不是以0开头。
# 样例
#
# numbers=[2, 7, 11, 15],  target=9
#
# return [1, 2]
# 注意
#
# 你可以假设只有一组答案。


class Solution:
    """
    @param numbers : An array of Integer
    @param target : target = numbers[index1] + numbers[index2]
    @return : [index1 + 1, index2 + 1] (index1 < index2)
    """

    def twoSum(self, numbers, target):
        # write your code here
        father = [item for item in numbers]
        numbers.sort()
        headIndex = 0
        tailIndex = len(numbers) - 1
        while headIndex < tailIndex:
            sum = numbers[headIndex] + numbers[tailIndex]
            if sum == target:
                h = father.index(numbers[headIndex])
                numbers[headIndex] = "a"
                t = father.index(numbers[tailIndex])
                if h > t:
                    h, t = t, h
                return [h + 1, t + 1]
            if sum > target:
                tailIndex -= 1
            if sum < target:
                headIndex += 1