原题地址

2401.png

方法一：双指针

双指针的典型题目。设左右指针

python3代码

  1. def twoSum(self, numbers: List[int], target: int) -> List[int]:
  2.     low, high = 0, len(numbers) - 1
  3.     while low < high:
  4.         if numbers[low] + numbers[high] == target:
  5.             return [low+1, high+1]
  6.         elif numbers[low] + numbers[high] > target:
  7.             high -= 1
  8.         else:
  9.             low += 1
  10.     return []

时间复杂度O(n)

空间复杂度O(1)

方法二：二分查找

从左到右遍历数组，固定第一个数，对第二个数进行二分查找

  1. def twoSum(self, numbers: List[int], target: int) -> List[int]:
  2.     n = len(numbers)
  3.     for i in range(n):
  4.         need = target - numbers[i]
  5.         left, right = i+1, n-1
  6.         while left <= right:
  7.             mid = int((left + right) / 2)
  8.             if numbers[mid] > need:
  9.                 right = mid - 1
  10.             elif numbers[mid] < need:
  11.                 left = mid + 1
  12.             else:
  13.                 return [i+1, mid+1]
  14.     return []

时间复杂度O(nlogn)

空间复杂度O(1)

方法三： 哈希表

  1. def twoSum(self, numbers: List[int], target: int) -> List[int]:
  2.     numDict = {}
  3.     for k, num in enumerate(numbers):
  4.         if numDict.get(target - num) is not None:
  5.             return [numDict[target-num]+1, k+1]
  6.         numDict[num] = k
  7.     return []

时间复杂度O(n)

空间复杂度O(n)