Leetcode 167. sum of two numbers II - input ordered array

Power button | 167. Sum of two numbers II - Input an ordered array

Title screenshot

Method 1 ： Violence law

The corresponding array can be found by two loops .

Violence law will fail the test because of overtime .

Be careful ： The problem requires a unique solution , And the same subscript cannot be repeated , So when the answer is two same numbers , Must return even different subscripts . So the outer layer is set to i stay 0 To n Between , The inner layer is set to j stay i+1 To n Between .

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        ans = [0]*2
        n = len(numbers)
        for left in range(0, n):
            for right in range(left+1, n):
                if numbers[left]+numbers[right] == target:
                    ans=[left+1, right+1]
        return ans

Complete test code

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        ans = [0]*2
        n = len(numbers)
        for left in range(0, n):
            for right in range(left+1, n):
                if numbers[left]+numbers[right] == target:
                    ans=[left+1, right+1]
        return ans

class main:
    a = Solution()
    numbers = [-1,0,4,4,6]
    target = 8
    b=a.twoSum(numbers, target)
    print(b)


if __name__ == '__main__':
    main()

Method 2 ： Two points search

It also uses the internal and external circulation , The difference is that the inner layer is dichotomy , In this way, the time complexity can be reduced .

The external circulation fixes the first number , Then the inner circle uses dichotomy to find the second number .

The first number is i, Left and right respectively i+1, and n-1. Then keep finding compromises .

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)

        for i in range(0, n):
            left, right = i + 1, n - 1
            while left <= right:
                mid = (left + right)//2
                if  numbers[mid] == target-numbers[i]:
                    return [i+1, mid+1]
                elif numbers[mid] > target-numbers[i]:
                    right = mid - 1
                else:
                    left = mid + 1

Method 3 ： Double pointer

Use double pointers directly , Move from both sides to the middle , Only one layer of circulation is needed . It greatly reduces the time complexity .

Set the left and right pointers to 0, and n-1, Move from both sides to the middle . If the sum value is found to be exactly equal to the target value , The subscript is returned . The subscript of the title is given from 1 Start , Computer subscript from 0 Start , Remember to subscript when returning +1.

If the sum value is found to be greater than the target value , Then the right pointer moves left . conversely , Move the pointer to the right .

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        left, right = 0, n - 1
        while left < right:
            if  numbers[left]+ numbers[right] == target:
                return [left+1, right+1]
            elif numbers[left]+ numbers[right] > target:
                right -= 1
            else:
                left += 1