1. 链表合并,可以递归
2. 匹配问题,前后收紧
3. 3个数加和的题,先排序,从左遍历,对每一位选最好的两个数的唯一解(两个指针,一次遍历),nlogn + n2 =n2
4. 同理,4个数
*
先排序,从左遍历,对每两位(i,j)选最好的两个数的唯一解(两个指针,一次遍历),nlogn + n3 =n3;
*
先排序,从左遍历,对每一位选最好的三个数的唯一解(三个指针,一次遍历),nlogn + n2 =n2,指针的移动逻辑比较复杂
l+m+r > target, 大了,收紧右边 r--
l+m+r < target, 小了,收紧左边(l 或者 m)
Target-l-m-r < m-l, 总差小于l到m的差,移动l, l++
Target-l-m-r < m-l, 总差大于于l到m的差,移动m, m++
退出条件,m, r相遇
L与m相遇时,同时往后移到最新
由于m走过的,l可能再走一次,所以还是n3...
网友评论