[1337c0d3 in Python] Two Sum II – Input array is sorted－kazi1@的部落格

Question:

Similar to Question [1. Two Sum], except that the input array is already sorted in ascending order.

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for x in xrange(len(nums) - 1):
   t = target - nums[x]
   left = x + 1
   right = len(nums) - 1
   while left < right:
       pivot = left + ((right - left) >> 1)
       if nums[pivot] < t:
           left = pivot + 1
       elif t < nums[pivot]:
           right = pivot - 1
       else
           return x+1, pivot+1
return 0, 0

O(n) runtime, O(1) space – Two pointers:

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = 0
right = len(nums) - 1
while left < right:
   if target < nums[left] + nums[right]:
       right -= 1
   elif nums[left] + nums[right] < target:
       left += 1
   else
       return left+1, right+1
return 0, 0
raise ValueError()