需要固定一个指针,再遍历另一个指针的都可以用双指针方法
对 👍,你理解得很对。
像 两数之和(Two Sum)这种问题里,外层确定一个数,内层要找另一个数,其实就可以用 双指针 来代替内层的遍历。
我给你举个最简单的例子:
问题
给定一个有序数组 nums = [1, 2, 3, 4, 6, 8]
,找出和为 7
的两个数。
方法 1:双重循环(O(n²))
nums = [1, 2, 3, 4, 6, 8]
target = 7for i in range(len(nums)):for j in range(i+1, len(nums)):if nums[i] + nums[j] == target:print(nums[i], nums[j])
输出:
3 4
方法 2:双指针(O(n))
因为数组有序,可以用双指针:
nums = [1, 2, 3, 4, 6, 8]
target = 7left, right = 0, len(nums) - 1 # 左右指针
while left < right:s = nums[left] + nums[right]if s == target:print(nums[left], nums[right])breakelif s < target: # 和小了,左边右移left += 1else: # 和大了,右边左移right -= 1
输出:
3 4
所以:
两层循环是“i 定第一个数,j 遍历后面所有数”;
双指针是“i 定第一个数,另一个直接用 left/right 搜索”。
👉 当你只需要两个数时,用双指针比两层循环更快。
要不要我帮你画一下这两个解法的“指针移动过程”,一步步对比?