对撞指针
对撞指针
问题描述
对撞指针是一种在有序数组中使用两个相向移动的指针来解决问题的技术。
通常，一个指针从左向右移动，另一个指针从右向左移动，直到满足特定条件或指针相遇。
两数之和
算法思想
- 在有序数组中使用左右指针
- 如果和大于目标值，右指针左移
- 如果和小于目标值，左指针右移
- 如果和等于目标值，找到答案
代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1}; // 1-based index
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
};
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1}; // 1-based index
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{};
}
}
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
curr_sum = numbers[left] + numbers[right]
if curr_sum == target:
return [left + 1, right + 1] # 1-based index
elif curr_sum < target:
left += 1
else:
right -= 1
return []
三数之和
算法思想
- 固定一个数，转化为两数之和
- 使用对撞指针查找另外两个数
- 注意去重和剪枝优化
- 时间复杂度
代码实现
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int n = nums.size();
if (n < 3) return result;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // 去重
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left+1]) left++; // 去重
while (left < right && nums[right] == nums[right-1]) right--; // 去重
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
};
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
if (n < 3) return result;
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // 去重
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left+1]) left++; // 去重
while (left < right && nums[right] == nums[right-1]) right--; // 去重
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
n = len(nums)
if n < 3:
return result
nums.sort()
for i in range(n - 2):
if i > 0 and nums[i] == nums[i-1]: # 去重
continue
left, right = i + 1, n - 1
while left < right:
curr_sum = nums[i] + nums[left] + nums[right]
if curr_sum == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: # 去重
left += 1
while left < right and nums[right] == nums[right-1]: # 去重
right -= 1
left += 1
right -= 1
elif curr_sum < 0:
left += 1
else:
right -= 1
return result
盛最多水的容器
算法思想
- 使用左右指针表示容器的两个边界
- 计算当前面积，更新最大值
- 移动较短的那个边界
- 时间复杂度
代码实现
class Solution {
public:
int maxArea(vector<int>& height) {
int maxArea = 0;
int left = 0, right = height.size() - 1;
while (left < right) {
int area = min(height[left], height[right]) * (right - left);
maxArea = max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
};
class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
int left = 0, right = height.length - 1;
while (left < right) {
int area = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = 0
left, right = 0, len(height) - 1
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
时间复杂度分析
| 两数之和 | ||
| 三数之和 | ||
| 盛水容器 | ||
| 回文判断 |
应用场景
- 有序数组的查找
- 数组元素的对撞
- 回文串的判断
- 区间和的计算
- 双向搜索的优化
注意事项
- 数组有序性的保证
- 重复元素的处理
- 边界条件的判断
- 指针移动的选择
- 结果去重的处理
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
华为开奖679人在聊