首页 > itarticle > 算法笔记: 力扣#167 两数之和 ii

算法笔记: 力扣#167 两数之和 ii

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        low, high = 0, len(numbers)-1
        while low < high:
            curSum = numbers[low] + numbers[high]
            if curSum == target:
                return low+1, high+1
            if curSum < target:
                low += 1
            else:
                high -= 1

Java 实现

class  {
    public int[] twoSum(int[] numbers, int target) {
        int[] ans = {-1, -1};
        int low = 0;
        int high = numbers.length - 1;
        while(low < high){
            int curSum = numbers[low] + numbers[high];
            if(curSum == target){
                ans[0] = low+1;
                ans[1] = high+1;
                break;
            }
            if(curSum < target){
                low ++;
            }else{
                high --;
            }
        }
        return ans;
    }
}

时间复杂度

O(n).

空间复杂度

O(1).

链接

167. Two Sum II - Input array is sorted
167. 两数之和 II - 输入有序数组
 (English version) Algorithm Notes: Leetcode#167 Two Sum 2 - Input array is sorted