力扣 | 167.两数之和 II - 输入有序数组

题目截图

方法一：暴力法

两次循环即可找到对应数组。

暴力法会因为超时而无法通过测试。

注意：题目要求必须是唯一解，且不可以重复同一下标，所以出现答案是两个相同数字时，必须返回连个不同的下标。所以循环的时候外层设为i在0到n之间，内层设置为j在i+1到n之间。

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

完整测试代码

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()

方法二：二分查找

也是利用内外两层循环，不同的是内层为二分法，这样时间复杂度可以降低。

外循环固定第一个数，然后内循环利用二分法找第二个数。

第一个数为i，左右分别i+1，和n-1。然后不断折中查找。

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

方法三：双指针

直接利用双指针，从两边向中间移动，只需要一层循环即可。大大降低了时间复杂度。

将左右指针设为0，和n-1，从两边向中间移动。如果发现相加值刚好等于目标值，则返回下标。题目给定下标从1开始，计算机下标从0开始，返回时记得下标+1。

如果发现相加值大于目标值，则右指针左移。反之，做指针右移。

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

最后

以上就是温柔冰棍为你收集整理的LeetCode #167.两数之和 II - 输入有序数组方法一：暴力法方法二：二分查找方法三：双指针的全部内容，希望文章能够帮你解决LeetCode #167.两数之和 II - 输入有序数组方法一：暴力法方法二：二分查找方法三：双指针所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。