# 001 Two Sum

__author__ = 'Libao Jin'
__date__ = 'December 18, 2015'

import time

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #  start_time = time.time()
        #  n = len(nums)
        #  i = 0
        #  while i < n - 1:
            #  j = i + 1
            #  if nums[i] > target:
                #  continue
            #  while j < n:
                #  if nums[i] + nums[j] > target:
                    #  break
                #  if nums[i] + nums[j] == target:
                    #  end_time = time.time()
                    #  periods = end_time - start_time
                    #  print(periods)
                    #  return [i + 1, j + 1]
                #  else:
                    #  j += 1
            #  i += 1

        start_time = time.time()
        n = len(nums)
        i = 0
        while i < n - 1:
            t = target - nums[i]
            if t in nums:
                j = nums.index(t)
                if j <= i:
                    j = i + 1
                    if nums[i] > target:
                        continue
                    while j < n:
                        if nums[i] + nums[j] == target:
                            end_time = time.time()
                            periods = end_time - start_time
                            print(periods)
                            return [i + 1, j + 1]
                        else:
                            j += 1
                    i += 1
                    continue
                else:
                    end_time = time.time()
                    periods = end_time - start_time
                    print(periods)
                    return [i + 1, j + 1]
            i += 1

if __name__ == '__main__':
    s = Solution()
    nums = [1, 2, 3, 4, 5]
    print(s.twoSum(nums, 3))
    print(s.twoSum(nums, 4))
    print(s.twoSum(nums, 5))
    print(s.twoSum(nums, 6))
    print(s.twoSum(nums, 7))
    print(s.twoSum(nums, 8))
    print(s.twoSum(nums, 9))
    nums = [-1, -2, -3, -4, -5]
    print(s.twoSum(nums, -8))

