引入双指针到底解决什么问题我目前对“双指针”的理解是在遍历数组、数字状态或候选区间时同时维护两个会移动的位置并让它们承担不同的职责。这样做的价值不只是代码里出现了两个变量而是每次移动都能根据题目的规律排除一批不可能的情况从而减少重复枚举。很多直接枚举的写法会产生两层、三层甚至四层循环。双指针并不能把所有问题都变成线性复杂度但在数据有序、结果具有单调性或者数组需要原地读写时它经常可以把一部分重复搜索压缩掉。本文整理八道题283 移动零、1089 复写零、202 快乐数、11 盛最多水的容器、611 有效三角形的个数、LCR 179 两数之和、15 三数之和、18 四数之和。范围主要集中在四种模式同向快慢指针一个指针读一个指针写从后向前的读写指针避免扩展写入时覆盖还没有读取的数据快慢指针判环把反复变化的数字状态看成一条路线排序后相向双指针根据和的大小、面积上限或不等式关系移动左右边界。这里的“原地”是指直接修改输入数组不额外创建一个同等规模的新数组“去重”是指避免同一个答案因为数组中出现重复数字而被加入多次。下面按题号逐题整理我对指针含义、移动理由和代码细节的理解。一、283. 移动零题目描述给定一个数组nums将数组中的所有0移动到数组末尾同时保持非零元素原来的相对顺序。要求直接修改输入数组也就是原地完成不能返回一个新的完整数组。例如[0, 1, 0, 3, 12]处理后变为[1, 3, 12, 0, 0]。题目链接LeetCode 283. 移动零算法思路这道题适合同向快慢指针。我的判断依据是题目要求把“满足条件的元素”集中到数组前面同时保留它们原来的顺序并且要求原地修改。可以把任务拆成两步先把所有非零数按原顺序写到数组前面再把剩余位置补成零。fast是读指针从左到右检查每一个元素slow是写指针表示下一个非零元素应该放在哪里每读到一个非零元素就写到nums[slow]然后让slow向右移动全部扫描结束后slow左侧已经放好了所有非零元素从slow开始到数组末尾全部填零。这里不需要在每遇到一个零时搬动后面的整段元素。那种做法虽然容易想到但多个零会反复搬动同一批数据最坏情况下会达到O(n²)。快慢指针把“寻找非零元素”和“放置非零元素”分开每个元素只被扫描和处理有限次。slow不会超过fast因此写入动作不会覆盖右侧还没有读到的元素。当slow和fast相等时当前非零元素相当于写回原处也不会有问题。Java代码class Solution { public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; slow; } } while (slow nums.length) { nums[slow] 0; slow; } } }代码说明slow初始为0表示第一个非零数应当写入的位置。fast扫描到非零值时nums[slow] nums[fast]将它写入当前应该保留的区域然后slow为下一个非零值预留位置。扫描结束时区间[0, slow)中已经按原有顺序放入所有非零数。这里的右边界slow不包含在已完成区域中所以从slow开始补零即可。例如输入[0, 1, 0, 3, 12]非零数依次是1、3、12它们会被写到下标0、1、2最后下标3、4写成零。复杂度与易错点时间复杂度O(n)。fast扫描数组一次补零最多再扫描一次整体仍是线性时间。空间复杂度O(1)只使用了几个额外变量。易错点主要有以下几个非零元素包括负数判断条件必须是nums[fast] ! 0。前移非零元素后不能忘记补零否则数组后半部分可能残留旧值。题目要求原地修改方法返回类型是void不是返回新数组。不能因为担心自己覆盖自己就写出复杂的交换逻辑slow fast时赋值是安全的。非零元素的相对顺序必须保持不能使用会改变顺序的随意交换方案。这道题让我先认识到一种很常见的双指针职责分工fast负责找slow负责放。后面的同向数组题也可以先从这个角度判断。二、1089. 复写零题目描述给定一个固定长度的数组arr每遇到一个零就在它后面复制一个零并将右侧元素依次向右移动。超出数组长度的元素会被丢弃。要求原地修改数组数组长度保持不变。例如[1, 0, 2, 3, 0, 4, 5, 0]处理后为[1, 0, 0, 2, 3, 0, 0, 4]。题目链接LeetCode 1089. 复写零算法思路这道题和移动零的区别在于元素不是被筛选后占一个位置而是零会额外占用一个位置。数组仍然是固定长度因此从前向后直接写会覆盖后面还没有读取的元素。我把它理解成一个“虚拟扩容数组”普通数字在虚拟数组中占一个位置零占两个位置。实际数组并没有真的扩容只是先按照这个规则计算每个原元素在虚拟数组中的位置。具体做法如下统计原数组中零的数量zeros。i从数组最后一个位置开始表示当前正在读取的原元素。j从虚拟扩容数组的末尾开始表示当前应该写入的虚拟位置。从后向前处理每个原元素。如果j落在真实数组范围内就写入nums[j] nums[i]。如果当前元素是零还需要让j再向左移动一格并在范围内写入第二个零。最后让i和j继续向左移动处理前一个原元素。从后向前写的好处是写入位置位于当前读取位置的右侧或者与当前读取位置重合不会破坏左侧尚未读取的内容。若虚拟位置已经超出真实数组边界只计算位置而不实际赋值。Java代码class Solution { public void duplicateZeros(int[] nums) { int zeros 0; for (int num : nums) { if (num 0) { zeros; } } int i nums.length - 1; int j nums.length zeros - 1; while (i 0) { if (j nums.length) { nums[j] nums[i]; } if (nums[i] 0) { j--; if (j nums.length) { nums[j] 0; } } i--; j--; } } }代码说明zeros表示所有零在虚拟数组中多占出来的格数因此虚拟数组最后一个下标是nums.length zeros - 1。i始终指向真实数组中还没有处理的原元素j指向这个原元素在虚拟布局中应该写入的位置。普通元素只占一格所以写完后j--零占两格所以先写一份再额外j--写第二份零最后再统一j--进入前一个原元素对应的区域。边界判断只在写入前进行。比如虚拟数组的末尾可能超过真实数组末尾这些位置虽然参与了计算但不能访问nums[j]。因此if (j nums.length)是避免数组越界的关键。复杂度与易错点时间复杂度O(n)。统计零一次倒序处理一次。空间复杂度O(1)。没有创建虚拟数组虚拟数组只是用来推导下标。易错点包括不能从前向后直接复制否则新写入的内容可能覆盖后面还没有读到的元素。j可能大于等于nums.length写入前必须检查范围。当前元素为零时需要额外向左移动一次并写入第二个零。“虚拟扩容”不等于真的创建一个更长的数组否则空间复杂度就不是常数了。有些边界位置的零复制后完全落在数组外只需要计算不需要写入。和移动零放在一起看二者都属于原地读写但方向相反如果写入不会增加元素数量可以从前向后用快慢指针如果一个元素可能扩展成多个位置并且前写会覆盖未读数据就更适合从后向前处理。三、202. 快乐数题目描述给定一个正整数n不断将它替换为各位数字的平方和。如果最终得到1那么这个数就是快乐数如果计算过程进入一个不包含1的循环则它不是快乐数。例如19 → 82 → 68 → 100 → 1所以19是快乐数。题目链接LeetCode 202. 快乐数算法思路这道题表面上没有数组下标但仍然可以使用快慢指针。每个数字都可以看成一个状态计算“各位数字平方和”就是从当前状态走向下一个状态。如果一个状态序列最终到达1由于1的下一个状态仍然是1所以它会进入1这个长度为一的环。如果不是快乐数序列也会进入另一个环。问题的关键就变成了状态序列是否成环以及相遇时的状态是不是1。做法是slow每次执行一次getNextfast每次执行两次getNext如果序列进入环快指针最终会追上慢指针相遇后判断相遇值是否为1。这里将数字状态当成链表节点getNext就类似于链表节点的next。快慢指针不一定只能操作数组或链表只要对象之间存在“下一步”的关系就可能用来判断环。Java代码class Solution { public boolean isHappy(int n) { int slow n; int fast getNext(n); while (slow ! fast) { slow getNext(slow); fast getNext(getNext(fast)); } return slow 1; } private int getNext(int n) { int sum 0; while (n 0) { int digit n % 10; sum digit * digit; n / 10; } return sum; } }代码说明getNext(int n)负责计算下一个状态。n % 10取出当前个位数字n / 10去掉个位循环结束时就得到了所有位数字平方和。这里将slow初始化为n将fast初始化为getNext(n)相当于让快指针先走一步。这样可以直接使用普通的while (slow ! fast)。如果两个指针都初始化为n则需要采用do...while或其他方式保证至少先执行一次移动。非快乐数2的变化过程会出现2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。再次遇到4就说明进入了循环快慢指针会在这个环中相遇而相遇值不是1。复杂度与易错点时间复杂度每次计算各位平方和需要处理数字的位数单次是O(log n)对于int范围的输入状态很快会进入一个有限的小范围整体可以按O(log n)级别理解。空间复杂度O(1)。易错点包括fast每轮必须走两步即getNext(getNext(fast))。不能只循环到n 1因为非快乐数会无限循环需要显式处理环。取个位使用% 10去掉个位使用/ 10。1本身是一个自环所以最后判断相遇值是否为1。另一种常见写法是用HashSet记录出现过的状态逻辑直观但需要O(n)级别的额外空间本题的快慢指针版本把辅助空间降到了O(1)。四、11. 盛最多水的容器题目描述给定一个整数数组height其中height[i]表示位于下标i的竖线高度。选择两条不同的竖线与横轴共同构成一个容器求这个容器能够盛放的最大水量。容器面积由两部分决定两条线之间的宽度以及两条线中较短的高度。面积公式是min(height[left], height[right]) * (right - left)。题目链接LeetCode 11. 盛最多水的容器算法思路这是相向双指针的典型题。开始时让left位于最左端、right位于最右端此时宽度最大。每一轮先计算当前容器面积再决定移动哪一侧。水位受到短板限制所以如果左边高度较小继续保留左边而只让右边向内移动时宽度一定会变小水位仍然不会超过当前左边的短板面积不可能超过当前这组边界的面积。因此左边较短时当前左边界对应的其他更窄组合都可以排除只有换掉左边、寻找更高的左边界才有可能产生更大的面积。右边较短时同理。这就是“移动短边”的依据不是一个脱离题目条件的固定口诀。它依赖于面积中的短板限制和宽度单调变小这两个事实。当两边一样高时移动任意一边都可以代码中选择移动左边。Java代码class Solution { public int maxArea(int[] height) { int left 0; int right height.length - 1; int ret 0; while (left right) { int width right - left; int minHeight Math.min(height[left], height[right]); int area width * minHeight; ret Math.max(ret, area); if (height[left] height[right]) { left; } else { right--; } } return ret; } }代码说明left和right表示当前还没有排除的两条边。宽度是下标差right - left不是元素个数所以不需要加一。每轮先通过Math.min求出短板高度再计算面积并更新ret。更新完当前组合后根据两边高度决定移动短边。循环条件是left right因为同一个下标不能形成有宽度的容器。例如数组[1,8,6,2,5,4,8,3,7]最初两端形成面积8。左边高度1是短板移动左指针后边界来到高度8此时与右端高度7形成面积7 * 7 49后续搜索不会得到更大结果。复杂度与易错点时间复杂度O(n)。每轮至少移动一个指针两个指针总共只向内移动有限次。空间复杂度O(1)。易错点包括水位是较短边的高度必须使用Math.min不能使用Math.max。宽度是right - left。先计算并更新当前面积再移动指针避免漏算当前边界组合。移动短边而不是长边长边被保留时宽度变小但短板上限没有改善。循环条件应为left right。int可以覆盖题目通常给出的面积范围但如果题目约束更大面积计算也需要检查是否应该使用long。五、611. 有效三角形的个数题目描述给定一个包含非负整数的数组nums统计从数组中选择三个下标后能够组成三角形的组合数量。相同数值如果来自不同下标仍然属于不同的下标组合需要分别计数。三角形成立的条件是两条较短边之和严格大于最长边。题目链接LeetCode 611. 有效三角形的个数算法思路直接使用三层循环会得到O(n³)。排序以后可以固定最长边再用左右指针批量统计满足条件的组合。先对数组升序排序。令i从数组末尾向前移动把nums[i]作为当前固定的最长边。剩下的两条边在[0, i - 1]中选择设置left 0指向当前最小候选边right i - 1指向当前最大的候选边。判断nums[left] nums[right] nums[i]如果成立由于数组已经有序left到right - 1的所有元素都不小于nums[left]它们和nums[right]组成的组合也都满足条件。因此可以一次增加right - left个答案然后让right--。如果不成立说明当前最小边太小。固定left时即使使用最大的另一条边nums[right]也不够只有让left变大才有机会满足条件。这里的批量计数是本题最重要的地方。排序带来的单调性让一次判断可以覆盖一整段候选而不是逐个检查。Java代码import java.util.Arrays; class Solution { public int triangleNumber(int[] nums) { Arrays.sort(nums); int ret 0; for (int i nums.length - 1; i 2; i--) { int left 0; int right i - 1; while (left right) { if (nums[left] nums[right] nums[i]) { ret right - left; right--; } else { left; } } } return ret; } }代码说明排序后固定的nums[i]是最长边所以只需要判断nums[left] nums[right] nums[i]。另外两组边之和一定不会更小因为nums[i]已经是三者中的最大值。条件成立时为什么增加right - left而不是right - left 1当前right已经被作为第二条边使用左边只能从left到right - 1选择共有right - left个下标。之后right--继续处理下一条可能的第二长边。条件不成立时当前left和最大的right都无法组成三角形因此保留这个left没有必要直接left。例如排序后的[2, 2, 3, 4]固定最长边4时3与两个2都能组成三角形一次计入两个组合固定最长边3时两个2又组成一个组合总数为3。这里相同的边长来自不同下标因此不能像三数之和那样按数值去重。复杂度与易错点时间复杂度排序为O(n log n)外层固定最长边并进行双指针扫描的部分为O(n²)总复杂度是O(n²)。空间复杂度除排序实现可能使用的栈空间外算法只使用常数个变量Java 中Arrays.sort(int[])的具体辅助空间取决于实现。易错点包括三角形条件是严格大于等于时只是退化成一条直线。条件成立时增加right - left不要把right自己重复算作左边。条件成立移动right条件不成立移动left方向不能写反。必须先排序否则无法使用批量统计的单调性。零会被严格不等式自然排除不必单独删除。本题统计的是下标组合不是不同数值组合重复数值来自不同下标时要分别计数。如果题目数据范围使答案可能超过int还需要根据题目约束选择更大的结果类型常规题目约束下int返回值符合题面要求。六、LCR 179. 两数之和题目描述给定一个已经按非递减顺序排列的数组price和目标值target找出两个数使它们的和等于target并返回这两个数。题目通常保证存在满足条件的答案返回的是数值而不是下标。题目链接LCR 179. 查找总价格为目标值的两个商品算法思路这是有序数组中的标准相向双指针。left从最小值开始right从最大值开始。每轮计算两端之和和等于target直接返回两个数和小于target需要让和变大所以移动left尝试更大的数和大于target需要让和变小所以移动right尝试更小的数。移动理由依赖于数组有序。如果当前和太小移动right只会让右侧数变小结果不可能变大因此当前left与这个right的组合以及更小的右侧组合都可以排除同理和太大时应排除当前right。如果数组无序就不能直接套用这套方向判断。无序数组通常需要哈希表或者先排序并同时保留原下标本题已经有序所以双指针可以用常数级额外空间完成。Java代码class Solution { public int[] twoSum(int[] price, int target) { int left 0; int right price.length - 1; while (left right) { int sum price[left] price[right]; if (sum target) { return new int[] {price[left], price[right]}; } else if (sum target) { left; } else { right--; } } return new int[0]; } }代码说明left和right始终指向两个不同位置所以循环条件为left right。当sum target时返回包含两个价格的数组而不是返回两个下标。以price [2, 7, 11, 15]、target 9为例开始时2 15 17和太大右指针向左移动接着2 11 13仍然太大右指针继续移动最后2 7 9返回[2, 7]。方法末尾的return new int[0]是为了覆盖“没有找到答案”的代码路径。题目如果保证答案存在正常执行时会在循环中返回这行不会影响核心算法。复杂度与易错点时间复杂度O(n)。两个指针都只向内移动不会反复回退。空间复杂度O(1)不计返回数组占用的固定空间。易错点包括这套移动方向建立在数组有序的前提上。sum target时移动leftsum target时移动right。left right保证不会重复使用同一个位置。LCR 179 返回的是两个数值不是下标和其他“两数之和”题目混淆时需要重新核对题面。如果题目约束中的数值可能使两数相加溢出int可以将sum声明为long常见约束下int通常足够。这道题让我更清楚地看到相向双指针的关键不是“左右各放一个指针”而是数组有序后当前和的大小能够决定哪一侧不再有可能。七、15. 三数之和题目描述给定一个整数数组nums找出所有和为0且不重复的三元组[nums[i], nums[left], nums[right]]。三元组中的三个元素必须来自三个不同下标答案中的组合顺序不重要。例如输入[-1, 0, 1, 2, -1, -4]结果为[[-1, -1, 2], [-1, 0, 1]]。题目链接LeetCode 15. 三数之和算法思路三数之和如果使用三层循环复杂度是O(n³)。排序后固定第一个数再在右侧区间用左右指针寻找另外两个数可以降到O(n²)。步骤如下先将数组升序排序。用i固定三元组中的第一个数。令left i 1、right nums.length - 1在剩余区间中寻找两数之和-nums[i]。计算三数和和小于0left尝试更大的数和大于0right--尝试更小的数和等于0加入结果然后左右指针都移动。为了不重复加入相同答案需要在固定层和命中答案后分别去重。“去重”在这里指的是答案值不能重复并不是说数组中相同元素只能使用一次。比如[-1, -1, 2]是合法答案因为两个-1来自两个不同下标。真正需要跳过的是当某一层固定的值与上一轮相同继续使用它只会生成已经处理过的答案。固定层去重写成i 0 nums[i] nums[i - 1]。找到一个答案后先让left和right--离开当前组合再跳过新的左右指针与刚使用值相同的元素。排序还有一个额外作用如果nums[i] 0那么后面的数也都大于零三数和不可能再回到零可以提前结束外层循环。Java代码import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger ret new ArrayList(); for (int i 0; i nums.length - 2; i) { if (i 0 nums[i] nums[i - 1]) { continue; } if (nums[i] 0) { break; } int left i 1; int right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { left; } else if (sum 0) { right--; } else { ret.add(Arrays.asList(nums[i], nums[left], nums[right])); left; right--; while (left right nums[left] nums[left - 1]) { left; } while (left right nums[right] nums[right 1]) { right--; } } } } return ret; } }代码说明排序后三元组会以非递减顺序出现因此相同答案中的数字排列也统一了。外层循环只需要保证i右边还有两个位置所以条件是i nums.length - 2。i 0 nums[i] nums[i - 1]只跳过同一层中连续重复的固定值不会影响使用重复数字组成合法答案。比如排序后的[-1, -1, 0, 1, 2]第一个-1已经作为固定值搜索过第二个-1作为固定值时会得到同样的答案因此跳过。在左右扫描中和偏小时左指针右移和偏大时右指针左移。命中答案后必须同时移动两个指针否则下一轮还会停在同一组数上。移动后再跳过相同值才能避免[0, 0, 0, 0]之类的数据产生重复三元组。复杂度与易错点时间复杂度排序为O(n log n)外层固定一个数、内层双指针扫描为O(n²)总复杂度为O(n²)。空间复杂度不计返回结果时主要是排序可能使用的栈空间结果列表占用的空间取决于答案数量。易错点包括固定层去重应比较nums[i]和nums[i - 1]不能比较后一个位置否则可能跳过合法答案。只有命中答案后才需要专门跳过左右两侧的重复值和偏小时或偏大时正常移动即可。命中后必须让left、right同时移动否则可能死循环或重复加入当前答案。left right保证三个下标互不相同。返回的是数值组合不是下标组合。Arrays.sort(nums)会改变输入数组本题的算法利用了这个变化。本题目标固定为0所以nums[i] 0时可以提前结束这个剪枝不能不加判断地套到目标值任意的四数之和中。八、18. 四数之和题目描述给定一个整数数组nums和目标值target找出所有总和等于target且不重复的四元组[nums[i], nums[j], nums[left], nums[right]]。四个元素必须来自四个不同下标。例如输入nums [1, 0, -1, 0, -2, 2]、target 0结果为[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]。题目链接LeetCode 18. 四数之和算法思路四数之和可以看成三数之和再增加一层固定下标先排序用i固定第一个数用j固定第二个数再用left和right在剩余区间中进行相向扫描。流程是升序排序使移动方向和去重都有依据。外层循环固定i并跳过同一层重复的nums[i]。内层循环固定j并只在当前i的范围内跳过重复的nums[j]。令left j 1、right nums.length - 1。计算四数和和小于target左指针右移和大于target右指针左移和等于target记录答案左右指针各移动一次再跳过重复值。这里必须使用long计算sum。即使方法参数和数组元素是int四个接近1_000_000_000的数相加也可能超过int的最大值。需要在加法开始前转换类型(long) nums[i] nums[j] nums[left] nums[right]。如果只把最终结果赋值给long而加法过程仍全部是int溢出已经发生后续再转换也无法恢复。四层去重分别对应固定i时跳过同层重复值固定j时跳过同一i下的重复值找到答案后跳过重复的left值找到答案后跳过重复的right值。Java代码import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListListInteger fourSum(int[] nums, int target) { Arrays.sort(nums); ListListInteger ret new ArrayList(); for (int i 0; i nums.length - 3; i) { if (i 0 nums[i] nums[i - 1]) { continue; } for (int j i 1; j nums.length - 2; j) { if (j i 1 nums[j] nums[j - 1]) { continue; } int left j 1; int right nums.length - 1; while (left right) { long sum (long) nums[i] nums[j] nums[left] nums[right]; if (sum target) { left; } else if (sum target) { right--; } else { ret.add(Arrays.asList( nums[i], nums[j], nums[left], nums[right])); left; right--; while (left right nums[left] nums[left - 1]) { left; } while (left right nums[right] nums[right 1]) { right--; } } } } } return ret; } }代码说明外层i右侧至少要剩下三个元素所以循环条件是i nums.length - 3。内层j右侧至少要剩下两个元素所以条件是j nums.length - 2。j的去重条件不能简单写成j 0。当j i 1时它是当前固定的i后面第一个候选位置即使数值与前面其他位置相同也不能跨越当前i的边界去跳过。正确的判断是j i 1 nums[j] nums[j - 1]表示只跳过同一个i下已经处理过的第二个数。相向扫描部分和三数之和相同和小就需要增大左侧数字和大就需要减小右侧数字。命中后同时移动左右指针再跳过重复数值。四个下标始终满足i j left right所以不会重复使用同一个数组位置。排序后加入结果的四个数天然是非递减顺序答案的表示也统一了。复杂度与易错点时间复杂度排序为O(n log n)两层固定下标约为O(n²)每组固定下标用双指针扫描为O(n)总复杂度为O(n³)。空间复杂度不计返回结果时主要是排序可能使用的栈空间结果列表占用的空间取决于答案数量。易错点包括四数和计算必须在加法开始前使用long推荐写成long sum (long) nums[i] nums[j] nums[left] nums[right]。i、j两个固定层都要去重命中后left、right也要去重。j的去重条件是j i 1不能写成只判断j 0。命中答案后要同时移动左右指针否则会停在原组合上。四个位置必须严格递增不能使用同一个下标两次。这里的target不一定是0不能直接照搬三数之和中nums[i] 0就结束的条件。先保证基础移动和去重逻辑正确再考虑上下界剪枝剪枝条件如果没有同步处理类型范围反而可能引入错误。九、八道题放在一起看双指针规律的归纳1. 快慢指针不只是一种写法283 移动零中的两个指针都从左向右但一个负责读取、一个负责写入202 快乐数中的两个指针也都沿着同一条状态路线前进但一个走一步、一个走两步1089 复写零则是从右向左完成读写。所以我现在不再只按变量名记忆“快慢指针”而是先问两个指针各自代表什么是不是一个负责读、一个负责写是否存在会重复出现的状态写入是否会让数据变长从而覆盖尚未读取的内容指针的移动方向和速度都是由这个职责决定的。2. 左右指针的前提是能够排除不可能情况LCR 179 中数组有序使得“和小增大左端、和大减小右端”成立11 盛最多水的容器中短板和宽度的关系使得移动长边没有机会超过当前面积611 有效三角形的个数中排序后的不等式让一次判断能够批量计数。因此看到两个边界并不意味着一定能用双指针。需要进一步确认移动一侧后是否真的能排除一批候选并且不会错过答案。3. 排序既是为了移动也是为了去重611、15、18 都先排序但使用排序的方式不完全相同三角形个数利用有序关系批量增加答案三数之和利用和的大小移动左右指针并对固定数和命中后的左右值去重四数之和在三数之和基础上多固定一层因此多了一层j的去重。排序还会改变输入数组原来的顺序这些题的题意允许这种变化。若题目要求保留原数组顺序就需要重新考虑是否可以排序。4. 去重是“同一层不重复”不是“相同数字不能使用”在三数之和和四数之和中相同数值来自不同下标时仍然可能组成合法答案。例如两个0可以同时参与一个答案。去重针对的是“同一个值组合已经被记录过”而不是把重复元素全部删除。外层固定值与同层前一个值相同就跳过内层固定值只在同一个外层固定值范围内跳过左右扫描命中后跳过与刚刚使用的数值相同的指针位置。611 则不同因为它统计下标组合的数量相同边长对应不同下标时需要分别计数不能使用三数之和的去重方式。5. 数值范围会影响指针题的正确性18 四数之和中指针方向本身没有问题但如果四个int先相加并溢出sum的大小就会变错后面的移动也会跟着错。使用long时类型转换必须发生在第一次加法之前。这提醒我算法逻辑和 Java 类型范围需要一起检查。代码看起来符合双指针模板并不代表在所有数值范围下都安全。十、这一组题形成的判断顺序现在遇到一个可能使用双指针的问题时我会按下面的顺序判断先确认目标是什么。是把某类元素集中到一侧、完成原地读写、判断状态是否成环还是寻找满足关系的两个或多个数。再说明每个指针的含义。一个指针是读、一个是写还是左右边界或者是状态序列中速度不同的两个位置。检查数据是否有序或者是否可以先排序。只有存在顺序和单调性才可能根据当前结果决定移动方向。写出移动依据。和小了为什么左移和大了为什么右移短板为什么需要更换条件成立时为什么可以批量计数。确定循环边界。两个指针能否指向同一位置通常决定使用还是固定了几个数也决定剩余区间至少要留几个位置。检查是否需要去重。返回所有数值组合时通常要处理重复答案统计下标组合时重复数值不一定需要跳过。检查写入方向和覆盖风险。原地扩展写入时前向写是否会覆盖未读数据如果会就考虑从后向前。检查类型和边界。多个整数相加是否可能溢出空数组、短数组、全零、全重复等情况是否会让指针初始化或循环条件失效。最后核对复杂度。统计每个指针总共移动多少次区分排序成本、外层固定成本和结果输出成本。这八道题放在一起后双指针对我们来说不再是单独的一组固定代码而是一种利用职责、顺序、单调性和排除关系来减少重复搜索的方法。代码中的left、right--或slow只有在移动理由清楚时才真正可靠。
双指针算法 题解总结
引入双指针到底解决什么问题我目前对“双指针”的理解是在遍历数组、数字状态或候选区间时同时维护两个会移动的位置并让它们承担不同的职责。这样做的价值不只是代码里出现了两个变量而是每次移动都能根据题目的规律排除一批不可能的情况从而减少重复枚举。很多直接枚举的写法会产生两层、三层甚至四层循环。双指针并不能把所有问题都变成线性复杂度但在数据有序、结果具有单调性或者数组需要原地读写时它经常可以把一部分重复搜索压缩掉。本文整理八道题283 移动零、1089 复写零、202 快乐数、11 盛最多水的容器、611 有效三角形的个数、LCR 179 两数之和、15 三数之和、18 四数之和。范围主要集中在四种模式同向快慢指针一个指针读一个指针写从后向前的读写指针避免扩展写入时覆盖还没有读取的数据快慢指针判环把反复变化的数字状态看成一条路线排序后相向双指针根据和的大小、面积上限或不等式关系移动左右边界。这里的“原地”是指直接修改输入数组不额外创建一个同等规模的新数组“去重”是指避免同一个答案因为数组中出现重复数字而被加入多次。下面按题号逐题整理我对指针含义、移动理由和代码细节的理解。一、283. 移动零题目描述给定一个数组nums将数组中的所有0移动到数组末尾同时保持非零元素原来的相对顺序。要求直接修改输入数组也就是原地完成不能返回一个新的完整数组。例如[0, 1, 0, 3, 12]处理后变为[1, 3, 12, 0, 0]。题目链接LeetCode 283. 移动零算法思路这道题适合同向快慢指针。我的判断依据是题目要求把“满足条件的元素”集中到数组前面同时保留它们原来的顺序并且要求原地修改。可以把任务拆成两步先把所有非零数按原顺序写到数组前面再把剩余位置补成零。fast是读指针从左到右检查每一个元素slow是写指针表示下一个非零元素应该放在哪里每读到一个非零元素就写到nums[slow]然后让slow向右移动全部扫描结束后slow左侧已经放好了所有非零元素从slow开始到数组末尾全部填零。这里不需要在每遇到一个零时搬动后面的整段元素。那种做法虽然容易想到但多个零会反复搬动同一批数据最坏情况下会达到O(n²)。快慢指针把“寻找非零元素”和“放置非零元素”分开每个元素只被扫描和处理有限次。slow不会超过fast因此写入动作不会覆盖右侧还没有读到的元素。当slow和fast相等时当前非零元素相当于写回原处也不会有问题。Java代码class Solution { public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; slow; } } while (slow nums.length) { nums[slow] 0; slow; } } }代码说明slow初始为0表示第一个非零数应当写入的位置。fast扫描到非零值时nums[slow] nums[fast]将它写入当前应该保留的区域然后slow为下一个非零值预留位置。扫描结束时区间[0, slow)中已经按原有顺序放入所有非零数。这里的右边界slow不包含在已完成区域中所以从slow开始补零即可。例如输入[0, 1, 0, 3, 12]非零数依次是1、3、12它们会被写到下标0、1、2最后下标3、4写成零。复杂度与易错点时间复杂度O(n)。fast扫描数组一次补零最多再扫描一次整体仍是线性时间。空间复杂度O(1)只使用了几个额外变量。易错点主要有以下几个非零元素包括负数判断条件必须是nums[fast] ! 0。前移非零元素后不能忘记补零否则数组后半部分可能残留旧值。题目要求原地修改方法返回类型是void不是返回新数组。不能因为担心自己覆盖自己就写出复杂的交换逻辑slow fast时赋值是安全的。非零元素的相对顺序必须保持不能使用会改变顺序的随意交换方案。这道题让我先认识到一种很常见的双指针职责分工fast负责找slow负责放。后面的同向数组题也可以先从这个角度判断。二、1089. 复写零题目描述给定一个固定长度的数组arr每遇到一个零就在它后面复制一个零并将右侧元素依次向右移动。超出数组长度的元素会被丢弃。要求原地修改数组数组长度保持不变。例如[1, 0, 2, 3, 0, 4, 5, 0]处理后为[1, 0, 0, 2, 3, 0, 0, 4]。题目链接LeetCode 1089. 复写零算法思路这道题和移动零的区别在于元素不是被筛选后占一个位置而是零会额外占用一个位置。数组仍然是固定长度因此从前向后直接写会覆盖后面还没有读取的元素。我把它理解成一个“虚拟扩容数组”普通数字在虚拟数组中占一个位置零占两个位置。实际数组并没有真的扩容只是先按照这个规则计算每个原元素在虚拟数组中的位置。具体做法如下统计原数组中零的数量zeros。i从数组最后一个位置开始表示当前正在读取的原元素。j从虚拟扩容数组的末尾开始表示当前应该写入的虚拟位置。从后向前处理每个原元素。如果j落在真实数组范围内就写入nums[j] nums[i]。如果当前元素是零还需要让j再向左移动一格并在范围内写入第二个零。最后让i和j继续向左移动处理前一个原元素。从后向前写的好处是写入位置位于当前读取位置的右侧或者与当前读取位置重合不会破坏左侧尚未读取的内容。若虚拟位置已经超出真实数组边界只计算位置而不实际赋值。Java代码class Solution { public void duplicateZeros(int[] nums) { int zeros 0; for (int num : nums) { if (num 0) { zeros; } } int i nums.length - 1; int j nums.length zeros - 1; while (i 0) { if (j nums.length) { nums[j] nums[i]; } if (nums[i] 0) { j--; if (j nums.length) { nums[j] 0; } } i--; j--; } } }代码说明zeros表示所有零在虚拟数组中多占出来的格数因此虚拟数组最后一个下标是nums.length zeros - 1。i始终指向真实数组中还没有处理的原元素j指向这个原元素在虚拟布局中应该写入的位置。普通元素只占一格所以写完后j--零占两格所以先写一份再额外j--写第二份零最后再统一j--进入前一个原元素对应的区域。边界判断只在写入前进行。比如虚拟数组的末尾可能超过真实数组末尾这些位置虽然参与了计算但不能访问nums[j]。因此if (j nums.length)是避免数组越界的关键。复杂度与易错点时间复杂度O(n)。统计零一次倒序处理一次。空间复杂度O(1)。没有创建虚拟数组虚拟数组只是用来推导下标。易错点包括不能从前向后直接复制否则新写入的内容可能覆盖后面还没有读到的元素。j可能大于等于nums.length写入前必须检查范围。当前元素为零时需要额外向左移动一次并写入第二个零。“虚拟扩容”不等于真的创建一个更长的数组否则空间复杂度就不是常数了。有些边界位置的零复制后完全落在数组外只需要计算不需要写入。和移动零放在一起看二者都属于原地读写但方向相反如果写入不会增加元素数量可以从前向后用快慢指针如果一个元素可能扩展成多个位置并且前写会覆盖未读数据就更适合从后向前处理。三、202. 快乐数题目描述给定一个正整数n不断将它替换为各位数字的平方和。如果最终得到1那么这个数就是快乐数如果计算过程进入一个不包含1的循环则它不是快乐数。例如19 → 82 → 68 → 100 → 1所以19是快乐数。题目链接LeetCode 202. 快乐数算法思路这道题表面上没有数组下标但仍然可以使用快慢指针。每个数字都可以看成一个状态计算“各位数字平方和”就是从当前状态走向下一个状态。如果一个状态序列最终到达1由于1的下一个状态仍然是1所以它会进入1这个长度为一的环。如果不是快乐数序列也会进入另一个环。问题的关键就变成了状态序列是否成环以及相遇时的状态是不是1。做法是slow每次执行一次getNextfast每次执行两次getNext如果序列进入环快指针最终会追上慢指针相遇后判断相遇值是否为1。这里将数字状态当成链表节点getNext就类似于链表节点的next。快慢指针不一定只能操作数组或链表只要对象之间存在“下一步”的关系就可能用来判断环。Java代码class Solution { public boolean isHappy(int n) { int slow n; int fast getNext(n); while (slow ! fast) { slow getNext(slow); fast getNext(getNext(fast)); } return slow 1; } private int getNext(int n) { int sum 0; while (n 0) { int digit n % 10; sum digit * digit; n / 10; } return sum; } }代码说明getNext(int n)负责计算下一个状态。n % 10取出当前个位数字n / 10去掉个位循环结束时就得到了所有位数字平方和。这里将slow初始化为n将fast初始化为getNext(n)相当于让快指针先走一步。这样可以直接使用普通的while (slow ! fast)。如果两个指针都初始化为n则需要采用do...while或其他方式保证至少先执行一次移动。非快乐数2的变化过程会出现2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。再次遇到4就说明进入了循环快慢指针会在这个环中相遇而相遇值不是1。复杂度与易错点时间复杂度每次计算各位平方和需要处理数字的位数单次是O(log n)对于int范围的输入状态很快会进入一个有限的小范围整体可以按O(log n)级别理解。空间复杂度O(1)。易错点包括fast每轮必须走两步即getNext(getNext(fast))。不能只循环到n 1因为非快乐数会无限循环需要显式处理环。取个位使用% 10去掉个位使用/ 10。1本身是一个自环所以最后判断相遇值是否为1。另一种常见写法是用HashSet记录出现过的状态逻辑直观但需要O(n)级别的额外空间本题的快慢指针版本把辅助空间降到了O(1)。四、11. 盛最多水的容器题目描述给定一个整数数组height其中height[i]表示位于下标i的竖线高度。选择两条不同的竖线与横轴共同构成一个容器求这个容器能够盛放的最大水量。容器面积由两部分决定两条线之间的宽度以及两条线中较短的高度。面积公式是min(height[left], height[right]) * (right - left)。题目链接LeetCode 11. 盛最多水的容器算法思路这是相向双指针的典型题。开始时让left位于最左端、right位于最右端此时宽度最大。每一轮先计算当前容器面积再决定移动哪一侧。水位受到短板限制所以如果左边高度较小继续保留左边而只让右边向内移动时宽度一定会变小水位仍然不会超过当前左边的短板面积不可能超过当前这组边界的面积。因此左边较短时当前左边界对应的其他更窄组合都可以排除只有换掉左边、寻找更高的左边界才有可能产生更大的面积。右边较短时同理。这就是“移动短边”的依据不是一个脱离题目条件的固定口诀。它依赖于面积中的短板限制和宽度单调变小这两个事实。当两边一样高时移动任意一边都可以代码中选择移动左边。Java代码class Solution { public int maxArea(int[] height) { int left 0; int right height.length - 1; int ret 0; while (left right) { int width right - left; int minHeight Math.min(height[left], height[right]); int area width * minHeight; ret Math.max(ret, area); if (height[left] height[right]) { left; } else { right--; } } return ret; } }代码说明left和right表示当前还没有排除的两条边。宽度是下标差right - left不是元素个数所以不需要加一。每轮先通过Math.min求出短板高度再计算面积并更新ret。更新完当前组合后根据两边高度决定移动短边。循环条件是left right因为同一个下标不能形成有宽度的容器。例如数组[1,8,6,2,5,4,8,3,7]最初两端形成面积8。左边高度1是短板移动左指针后边界来到高度8此时与右端高度7形成面积7 * 7 49后续搜索不会得到更大结果。复杂度与易错点时间复杂度O(n)。每轮至少移动一个指针两个指针总共只向内移动有限次。空间复杂度O(1)。易错点包括水位是较短边的高度必须使用Math.min不能使用Math.max。宽度是right - left。先计算并更新当前面积再移动指针避免漏算当前边界组合。移动短边而不是长边长边被保留时宽度变小但短板上限没有改善。循环条件应为left right。int可以覆盖题目通常给出的面积范围但如果题目约束更大面积计算也需要检查是否应该使用long。五、611. 有效三角形的个数题目描述给定一个包含非负整数的数组nums统计从数组中选择三个下标后能够组成三角形的组合数量。相同数值如果来自不同下标仍然属于不同的下标组合需要分别计数。三角形成立的条件是两条较短边之和严格大于最长边。题目链接LeetCode 611. 有效三角形的个数算法思路直接使用三层循环会得到O(n³)。排序以后可以固定最长边再用左右指针批量统计满足条件的组合。先对数组升序排序。令i从数组末尾向前移动把nums[i]作为当前固定的最长边。剩下的两条边在[0, i - 1]中选择设置left 0指向当前最小候选边right i - 1指向当前最大的候选边。判断nums[left] nums[right] nums[i]如果成立由于数组已经有序left到right - 1的所有元素都不小于nums[left]它们和nums[right]组成的组合也都满足条件。因此可以一次增加right - left个答案然后让right--。如果不成立说明当前最小边太小。固定left时即使使用最大的另一条边nums[right]也不够只有让left变大才有机会满足条件。这里的批量计数是本题最重要的地方。排序带来的单调性让一次判断可以覆盖一整段候选而不是逐个检查。Java代码import java.util.Arrays; class Solution { public int triangleNumber(int[] nums) { Arrays.sort(nums); int ret 0; for (int i nums.length - 1; i 2; i--) { int left 0; int right i - 1; while (left right) { if (nums[left] nums[right] nums[i]) { ret right - left; right--; } else { left; } } } return ret; } }代码说明排序后固定的nums[i]是最长边所以只需要判断nums[left] nums[right] nums[i]。另外两组边之和一定不会更小因为nums[i]已经是三者中的最大值。条件成立时为什么增加right - left而不是right - left 1当前right已经被作为第二条边使用左边只能从left到right - 1选择共有right - left个下标。之后right--继续处理下一条可能的第二长边。条件不成立时当前left和最大的right都无法组成三角形因此保留这个left没有必要直接left。例如排序后的[2, 2, 3, 4]固定最长边4时3与两个2都能组成三角形一次计入两个组合固定最长边3时两个2又组成一个组合总数为3。这里相同的边长来自不同下标因此不能像三数之和那样按数值去重。复杂度与易错点时间复杂度排序为O(n log n)外层固定最长边并进行双指针扫描的部分为O(n²)总复杂度是O(n²)。空间复杂度除排序实现可能使用的栈空间外算法只使用常数个变量Java 中Arrays.sort(int[])的具体辅助空间取决于实现。易错点包括三角形条件是严格大于等于时只是退化成一条直线。条件成立时增加right - left不要把right自己重复算作左边。条件成立移动right条件不成立移动left方向不能写反。必须先排序否则无法使用批量统计的单调性。零会被严格不等式自然排除不必单独删除。本题统计的是下标组合不是不同数值组合重复数值来自不同下标时要分别计数。如果题目数据范围使答案可能超过int还需要根据题目约束选择更大的结果类型常规题目约束下int返回值符合题面要求。六、LCR 179. 两数之和题目描述给定一个已经按非递减顺序排列的数组price和目标值target找出两个数使它们的和等于target并返回这两个数。题目通常保证存在满足条件的答案返回的是数值而不是下标。题目链接LCR 179. 查找总价格为目标值的两个商品算法思路这是有序数组中的标准相向双指针。left从最小值开始right从最大值开始。每轮计算两端之和和等于target直接返回两个数和小于target需要让和变大所以移动left尝试更大的数和大于target需要让和变小所以移动right尝试更小的数。移动理由依赖于数组有序。如果当前和太小移动right只会让右侧数变小结果不可能变大因此当前left与这个right的组合以及更小的右侧组合都可以排除同理和太大时应排除当前right。如果数组无序就不能直接套用这套方向判断。无序数组通常需要哈希表或者先排序并同时保留原下标本题已经有序所以双指针可以用常数级额外空间完成。Java代码class Solution { public int[] twoSum(int[] price, int target) { int left 0; int right price.length - 1; while (left right) { int sum price[left] price[right]; if (sum target) { return new int[] {price[left], price[right]}; } else if (sum target) { left; } else { right--; } } return new int[0]; } }代码说明left和right始终指向两个不同位置所以循环条件为left right。当sum target时返回包含两个价格的数组而不是返回两个下标。以price [2, 7, 11, 15]、target 9为例开始时2 15 17和太大右指针向左移动接着2 11 13仍然太大右指针继续移动最后2 7 9返回[2, 7]。方法末尾的return new int[0]是为了覆盖“没有找到答案”的代码路径。题目如果保证答案存在正常执行时会在循环中返回这行不会影响核心算法。复杂度与易错点时间复杂度O(n)。两个指针都只向内移动不会反复回退。空间复杂度O(1)不计返回数组占用的固定空间。易错点包括这套移动方向建立在数组有序的前提上。sum target时移动leftsum target时移动right。left right保证不会重复使用同一个位置。LCR 179 返回的是两个数值不是下标和其他“两数之和”题目混淆时需要重新核对题面。如果题目约束中的数值可能使两数相加溢出int可以将sum声明为long常见约束下int通常足够。这道题让我更清楚地看到相向双指针的关键不是“左右各放一个指针”而是数组有序后当前和的大小能够决定哪一侧不再有可能。七、15. 三数之和题目描述给定一个整数数组nums找出所有和为0且不重复的三元组[nums[i], nums[left], nums[right]]。三元组中的三个元素必须来自三个不同下标答案中的组合顺序不重要。例如输入[-1, 0, 1, 2, -1, -4]结果为[[-1, -1, 2], [-1, 0, 1]]。题目链接LeetCode 15. 三数之和算法思路三数之和如果使用三层循环复杂度是O(n³)。排序后固定第一个数再在右侧区间用左右指针寻找另外两个数可以降到O(n²)。步骤如下先将数组升序排序。用i固定三元组中的第一个数。令left i 1、right nums.length - 1在剩余区间中寻找两数之和-nums[i]。计算三数和和小于0left尝试更大的数和大于0right--尝试更小的数和等于0加入结果然后左右指针都移动。为了不重复加入相同答案需要在固定层和命中答案后分别去重。“去重”在这里指的是答案值不能重复并不是说数组中相同元素只能使用一次。比如[-1, -1, 2]是合法答案因为两个-1来自两个不同下标。真正需要跳过的是当某一层固定的值与上一轮相同继续使用它只会生成已经处理过的答案。固定层去重写成i 0 nums[i] nums[i - 1]。找到一个答案后先让left和right--离开当前组合再跳过新的左右指针与刚使用值相同的元素。排序还有一个额外作用如果nums[i] 0那么后面的数也都大于零三数和不可能再回到零可以提前结束外层循环。Java代码import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger ret new ArrayList(); for (int i 0; i nums.length - 2; i) { if (i 0 nums[i] nums[i - 1]) { continue; } if (nums[i] 0) { break; } int left i 1; int right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { left; } else if (sum 0) { right--; } else { ret.add(Arrays.asList(nums[i], nums[left], nums[right])); left; right--; while (left right nums[left] nums[left - 1]) { left; } while (left right nums[right] nums[right 1]) { right--; } } } } return ret; } }代码说明排序后三元组会以非递减顺序出现因此相同答案中的数字排列也统一了。外层循环只需要保证i右边还有两个位置所以条件是i nums.length - 2。i 0 nums[i] nums[i - 1]只跳过同一层中连续重复的固定值不会影响使用重复数字组成合法答案。比如排序后的[-1, -1, 0, 1, 2]第一个-1已经作为固定值搜索过第二个-1作为固定值时会得到同样的答案因此跳过。在左右扫描中和偏小时左指针右移和偏大时右指针左移。命中答案后必须同时移动两个指针否则下一轮还会停在同一组数上。移动后再跳过相同值才能避免[0, 0, 0, 0]之类的数据产生重复三元组。复杂度与易错点时间复杂度排序为O(n log n)外层固定一个数、内层双指针扫描为O(n²)总复杂度为O(n²)。空间复杂度不计返回结果时主要是排序可能使用的栈空间结果列表占用的空间取决于答案数量。易错点包括固定层去重应比较nums[i]和nums[i - 1]不能比较后一个位置否则可能跳过合法答案。只有命中答案后才需要专门跳过左右两侧的重复值和偏小时或偏大时正常移动即可。命中后必须让left、right同时移动否则可能死循环或重复加入当前答案。left right保证三个下标互不相同。返回的是数值组合不是下标组合。Arrays.sort(nums)会改变输入数组本题的算法利用了这个变化。本题目标固定为0所以nums[i] 0时可以提前结束这个剪枝不能不加判断地套到目标值任意的四数之和中。八、18. 四数之和题目描述给定一个整数数组nums和目标值target找出所有总和等于target且不重复的四元组[nums[i], nums[j], nums[left], nums[right]]。四个元素必须来自四个不同下标。例如输入nums [1, 0, -1, 0, -2, 2]、target 0结果为[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]。题目链接LeetCode 18. 四数之和算法思路四数之和可以看成三数之和再增加一层固定下标先排序用i固定第一个数用j固定第二个数再用left和right在剩余区间中进行相向扫描。流程是升序排序使移动方向和去重都有依据。外层循环固定i并跳过同一层重复的nums[i]。内层循环固定j并只在当前i的范围内跳过重复的nums[j]。令left j 1、right nums.length - 1。计算四数和和小于target左指针右移和大于target右指针左移和等于target记录答案左右指针各移动一次再跳过重复值。这里必须使用long计算sum。即使方法参数和数组元素是int四个接近1_000_000_000的数相加也可能超过int的最大值。需要在加法开始前转换类型(long) nums[i] nums[j] nums[left] nums[right]。如果只把最终结果赋值给long而加法过程仍全部是int溢出已经发生后续再转换也无法恢复。四层去重分别对应固定i时跳过同层重复值固定j时跳过同一i下的重复值找到答案后跳过重复的left值找到答案后跳过重复的right值。Java代码import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListListInteger fourSum(int[] nums, int target) { Arrays.sort(nums); ListListInteger ret new ArrayList(); for (int i 0; i nums.length - 3; i) { if (i 0 nums[i] nums[i - 1]) { continue; } for (int j i 1; j nums.length - 2; j) { if (j i 1 nums[j] nums[j - 1]) { continue; } int left j 1; int right nums.length - 1; while (left right) { long sum (long) nums[i] nums[j] nums[left] nums[right]; if (sum target) { left; } else if (sum target) { right--; } else { ret.add(Arrays.asList( nums[i], nums[j], nums[left], nums[right])); left; right--; while (left right nums[left] nums[left - 1]) { left; } while (left right nums[right] nums[right 1]) { right--; } } } } } return ret; } }代码说明外层i右侧至少要剩下三个元素所以循环条件是i nums.length - 3。内层j右侧至少要剩下两个元素所以条件是j nums.length - 2。j的去重条件不能简单写成j 0。当j i 1时它是当前固定的i后面第一个候选位置即使数值与前面其他位置相同也不能跨越当前i的边界去跳过。正确的判断是j i 1 nums[j] nums[j - 1]表示只跳过同一个i下已经处理过的第二个数。相向扫描部分和三数之和相同和小就需要增大左侧数字和大就需要减小右侧数字。命中后同时移动左右指针再跳过重复数值。四个下标始终满足i j left right所以不会重复使用同一个数组位置。排序后加入结果的四个数天然是非递减顺序答案的表示也统一了。复杂度与易错点时间复杂度排序为O(n log n)两层固定下标约为O(n²)每组固定下标用双指针扫描为O(n)总复杂度为O(n³)。空间复杂度不计返回结果时主要是排序可能使用的栈空间结果列表占用的空间取决于答案数量。易错点包括四数和计算必须在加法开始前使用long推荐写成long sum (long) nums[i] nums[j] nums[left] nums[right]。i、j两个固定层都要去重命中后left、right也要去重。j的去重条件是j i 1不能写成只判断j 0。命中答案后要同时移动左右指针否则会停在原组合上。四个位置必须严格递增不能使用同一个下标两次。这里的target不一定是0不能直接照搬三数之和中nums[i] 0就结束的条件。先保证基础移动和去重逻辑正确再考虑上下界剪枝剪枝条件如果没有同步处理类型范围反而可能引入错误。九、八道题放在一起看双指针规律的归纳1. 快慢指针不只是一种写法283 移动零中的两个指针都从左向右但一个负责读取、一个负责写入202 快乐数中的两个指针也都沿着同一条状态路线前进但一个走一步、一个走两步1089 复写零则是从右向左完成读写。所以我现在不再只按变量名记忆“快慢指针”而是先问两个指针各自代表什么是不是一个负责读、一个负责写是否存在会重复出现的状态写入是否会让数据变长从而覆盖尚未读取的内容指针的移动方向和速度都是由这个职责决定的。2. 左右指针的前提是能够排除不可能情况LCR 179 中数组有序使得“和小增大左端、和大减小右端”成立11 盛最多水的容器中短板和宽度的关系使得移动长边没有机会超过当前面积611 有效三角形的个数中排序后的不等式让一次判断能够批量计数。因此看到两个边界并不意味着一定能用双指针。需要进一步确认移动一侧后是否真的能排除一批候选并且不会错过答案。3. 排序既是为了移动也是为了去重611、15、18 都先排序但使用排序的方式不完全相同三角形个数利用有序关系批量增加答案三数之和利用和的大小移动左右指针并对固定数和命中后的左右值去重四数之和在三数之和基础上多固定一层因此多了一层j的去重。排序还会改变输入数组原来的顺序这些题的题意允许这种变化。若题目要求保留原数组顺序就需要重新考虑是否可以排序。4. 去重是“同一层不重复”不是“相同数字不能使用”在三数之和和四数之和中相同数值来自不同下标时仍然可能组成合法答案。例如两个0可以同时参与一个答案。去重针对的是“同一个值组合已经被记录过”而不是把重复元素全部删除。外层固定值与同层前一个值相同就跳过内层固定值只在同一个外层固定值范围内跳过左右扫描命中后跳过与刚刚使用的数值相同的指针位置。611 则不同因为它统计下标组合的数量相同边长对应不同下标时需要分别计数不能使用三数之和的去重方式。5. 数值范围会影响指针题的正确性18 四数之和中指针方向本身没有问题但如果四个int先相加并溢出sum的大小就会变错后面的移动也会跟着错。使用long时类型转换必须发生在第一次加法之前。这提醒我算法逻辑和 Java 类型范围需要一起检查。代码看起来符合双指针模板并不代表在所有数值范围下都安全。十、这一组题形成的判断顺序现在遇到一个可能使用双指针的问题时我会按下面的顺序判断先确认目标是什么。是把某类元素集中到一侧、完成原地读写、判断状态是否成环还是寻找满足关系的两个或多个数。再说明每个指针的含义。一个指针是读、一个是写还是左右边界或者是状态序列中速度不同的两个位置。检查数据是否有序或者是否可以先排序。只有存在顺序和单调性才可能根据当前结果决定移动方向。写出移动依据。和小了为什么左移和大了为什么右移短板为什么需要更换条件成立时为什么可以批量计数。确定循环边界。两个指针能否指向同一位置通常决定使用还是固定了几个数也决定剩余区间至少要留几个位置。检查是否需要去重。返回所有数值组合时通常要处理重复答案统计下标组合时重复数值不一定需要跳过。检查写入方向和覆盖风险。原地扩展写入时前向写是否会覆盖未读数据如果会就考虑从后向前。检查类型和边界。多个整数相加是否可能溢出空数组、短数组、全零、全重复等情况是否会让指针初始化或循环条件失效。最后核对复杂度。统计每个指针总共移动多少次区分排序成本、外层固定成本和结果输出成本。这八道题放在一起后双指针对我们来说不再是单独的一组固定代码而是一种利用职责、顺序、单调性和排除关系来减少重复搜索的方法。代码中的left、right--或slow只有在移动理由清楚时才真正可靠。
