多指针 - wenzhoullq/leetcode GitHub Wiki
双指针模拟
题目
1537. 最大得分公共部分取较大
1754. 构造字典序最大的合并字符串用a.compareto(b)
2444. 统计定界子数组的数目 三指针维护
E. Two Platforms-2023.1.17-灵茶 维护一个最大值的思想需要学习
1616. 分割两个字符串得到回文串 前后缀越回文，中间部分越回文
排序
while(i+1<nums.length&&nums[i]==nums[i+1])
题目
- 摆动排序
选择较大部分保持绝对性
- 去除目标
原地排序
模板
原地排序的关键词在于 时间复杂度为O(n)并且额外的空间为O(1),数字在[0,n]是充分不必要条件
最外层一个for循环，如果有[0,n]的条件，那么这里的下标就替代指针了；如果没有则里面设置两个指针，分别指向left（0）和right（nums.length-1）
for(int i=0;i<nums.length;i++){
while(nums[i]<nums.length&&nums[i]>0&&nums[i]!=i+1&&nums[nums[i]-1]!=nums[i]){//关键在于这个while而不是if,因为交换过来的数字还得需要继续交换
int temp=nums[i];
nums[i]=nums[temp-1];
nums[temp-1]=temp;
}
}
题目
多指针求和
分析
多指针求和需要先排序，然后固定n个指针，剩下的进行遍历，然后因为去重的需求，因此考虑去重的代码
模板
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int left=i+1,right=nums.length-1,target=nums[i]*-1;
while(left<right){
if(nums[left]+nums[right]<target) left++;
else if(nums[left]+nums[right]>target) right--;
else {
while(left+1<right&&nums[left]==nums[left+1]) left++;// 关键点在相等的时候进行去重
while(left+1<right&&nums[right]==nums[right-1]) right--;
ans.add(Arrays.asList(new Integer[]{nums[i],nums[left],nums[right]}));
left++;
right--;
}
}
while(i+1<nums.length&&nums[i]==nums[i+1]) i++;//指针去重
}
return ans;
题目
1. 两数之和 这个是非模板的题，但是也只有这题是特殊的
模拟
多指针模拟,无固定模板