思想:双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。
题意解读:从数组中找出满足相加之和等于目标数的两个数——本质是遍历数组。
存在前提假设: 只有唯一的答案,不会使用相同的元素,这就决定了遍历一遍数组就可以实现
注意:每步两边指针如何变化
题意解读:题设要满足a的平方和 + b的平方和 = c, 所以a和b都应该小于等于c开方,遍历a和b之间的数,如果和小了a就增大,如果和大了b就减小。如果找不到这样的两个数,就返回false。
题意解读:遇到元音字母就反转
题意解读:一个字符串s,可以从中删除一个字符,判断能否成为回文字符串。
正常思路:删除一个元素,检查是不是回文串
改进:先判断,到元素不相等的地方跳过一个元素继续判断——减少很多重复操作
题意解读:两个非递减整数数组,按非递减顺序合并到原第一个数组
正常思路:开辟一个辅助空间,双指针,一个指向第一个数组,一个指向第二个数组,比较数字的大小,移动指针位置
改进思路:不开辟额外的空间,从后向前进行遍历
题意解读:判断链表中是否有环
思路1:hash表,讲节点放在表中,遍历一遍看是否有重复
思路2:快慢指针,如果存在环,快指针一定会追上慢指针
题意解读:任意删除字符串中的字符,找到字典中匹配且长度最长的,如果长度相同,返回字符串排序最小的
正常思路:字符串与字典中的每个字符串使用双指针
改进:动态规划——还没看懂
保证每次操作都是局部最优的,并且最后得到的结果是全局最优的