Python solution with detailed explanation


  • 0
    G

    Solution

    Two Sum II - Input array is sorted https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?tab=Description

    Binary Search

    • For every element x, search its complement using binary search.
    class Solution(object):
        def b_search(self, nums, low, high, target):
            while low <= high:
                mid = low + ((high-low)>>1)
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    high = mid - 1
                else:
                    low = mid + 1
            return -1
        
        def twoSum(self, numbers, target):
            """
            :type numbers: List[int]
            :type target: int
            :rtype: List[int]
            """
            result = []
            high = len(numbers)-1
            for i in range(len(numbers)):
                comp = target-numbers[i]
                idx = self.b_search(numbers, i+1, high, comp)
                if idx != -1:
                    result.append(i+1)
                    result.append(idx+1)                
                    break
            return result
    

    Two Pointers

    • Keep 2 pointers start and end and keep adjusting them.
    class Solution(object):
        def twoSum(self, numbers, target):
            """
            :type numbers: List[int]
            :type target: int
            :rtype: List[int]
            """
            s,e = 0, len(numbers)-1
            while s < e:
                if numbers[s] + numbers[e] == target:
                    return [s+1, e+1]
                elif numbers[s] + numbers[e] < target:
                    s = s+1
                else:
                    e = e-1
            return [None, None]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.