Leecode之双指针及二分查找

题目

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9

输出: [1,2]

解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：双指针

思路

    主要是在头尾各设置一个指针，然后进行求和，如果大于，则尾指针减一；如果小于，则头指针加一；否则，输出索引值

class Solution:

    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        length = len(numbers)

        right = length - 1

        left = 0

        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

解法二：二分查找

思路

拖了两天才搞明白这个问题，其实到头来只是自己没搞懂python函数调用和递归实现的方法。

首先你要明白这题查找只是第一步，首先利用二分查找找到target - numbers[left],然后再把Index传过来，赋值给right，这样各加一就可以得到答案了。第一种方法是网友给的解法，直接用while 循环找到值，然后返回索引。而第二种方法我用到了递归实现二分查找，速度比循环慢一些。下面是代码

### 方法一（循环实现二分查找）：

class Solution:

    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        length = len(numbers)

        for left in range(length - 1):

            right = self.binary_chop(numbers, left + 1, length - 1, target - numbers[left])

            if right != -1:

                return [left + 1, right + 1]

     def binary_chop(self, numbers, left, right, target):

         # 在子区间 [left, right] 找 target

         while left < right:

             mid = (left + right) //2

             if numbers[mid] < target:

                 left = mid + 1

             else:

                 right = mid

         return left if numbers[left] == target else -1  

###方法二（递归实现二分查找）：

class Solution:

    def twoSum(self, numbers: List[int], target: int) -> List[int]:

        length = len(numbers)

        for left in range(length - 1): #对列表进行遍历

            right = self.binary_chop(numbers, left + 1, length - 1, target - numbers[left]) #调用函数找值，返回Index赋值给right

            if right != -1: # 返回值不是-1时，找到位置

                return [left + 1, right + 1]

    def binary_chop(self, numbers, left, right, target):

        mid = (left + right) // 2

        if left < right:

            if numbers[mid] > target:

                return self.binary_chop(numbers, left, mid - 1, target)

            elif numbers[mid] < target:

                return self.binary_chop(numbers, mid + 1, right, target)

            else:

                return mid

        return left if numbers[left] == target else -1

巴特西

Leecode之双指针及二分查找

题目

解法一：双指针

思路

解法二：二分查找

最新文章

热门文章