双指针三数之和python
时间: 2024-10-16 12:09:09 浏览: 2
双指针算法是一种常见的数组处理技巧,它通常用于解决排序、查找、区间判断等问题。在Python中,"三数之和"的问题通常涉及到在一个数组中找到三个元素,使得它们的和等于给定的目标值。你可以使用两个指针(i和j)从数组的起始位置开始遍历,另一个辅助指针k用于跟踪当前目标值与前两个元素之差。
这是一个基本的解决方案:
```python
def threeSum(nums, target):
nums.sort() # 先对数组进行排序
n = len(nums)
res = [] # 存储结果
for i in range(n - 2): # 第一个指针i
if i > 0 and nums[i] == nums[i - 1]: # 避免重复元素
continue
left, right = i + 1, n - 1 # 第二个和第三个指针
while left < right: # 使用两个指针寻找和为目标值的元素
sum_ = nums[i] + nums[left] + nums[right]
if sum_ == target:
res.append([nums[i], nums[left], nums[right]])
# 如果找到了,左移右移缩小范围
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
elif sum_ < target:
left += 1 # 和小了,增大左侧指针
else:
right -= 1 # 和大了,减小右侧指针
return res
# 示例
nums = [-1, 0, 1, 2, -1, -4]
target = 0
print(threeSum(nums, target)) # 输出: [[-1, 0, 1]]
```
阅读全文