15. 16. 923. | 双指针题型

分析：

  题目要求计算三个数之和为零，且这三元组不能重复。联想到之前做过的“两数之和”，我们可以先将数组排序，再将数组拆分成两个部分来计算：

• 快慢指针：慢指针从起始遍历到结束，记录当前元素；快指针部分则对剩余元素进行“对撞指针”算法。

• 对撞指针：左指针和右指针分别从数组左右两端遍历，计算结果。

  此题的一个难点是理清各种边界问题，重复元素问题：

• 当数组长度小于3时，可以直接返回空结果。

• 在快慢指针循环中，若当前元素和前一个元素相同，则跳过该元素，不做计算；且若当前元素已经大于0，直接返回已经计算好的结果（因为后面的元素不可能再有三个相加为0的可能性）。

• 在对撞指针循环中，若右指针元素与前一个元素相同，则right--；若左指针元素与后一个元素相同，则left++；

分析：

  和上一题相似的解题过程，我们只需要把对撞指针部分换成判断距离是否更小就可以。

  此外，这题其实可以考虑一下在双指针的基础上进一步优化，比如去重、当距离为0可直接返回结果等。

分析：

  还是老方法，直接将题目拆解成快慢指针和对撞指针两个部分。题目要求三元组的全部排列组合结果，因此我们可以将解题步骤归纳成以下几个步骤：

• 数组排序，进入快慢指针循环；

• 当三元组和等于target时，计算相同元素的所有排列组合结果；

• 当三元组和大于target时，对撞指针的右指针往左移动；

• 当三元组和小于target时，对撞指针的左指针往右移动；

• 慢指针往右移动，直到遍历结束。

  该题的难点在于排列组合的计算，如[1,1,2,2,3,3]，target = 6，我们需要分别遍历计算2和3的个数，然后利用排列组合计算公式算出他们跟1一共有几种组合情况。

• while(condition) left++，计算2的个数

• while(condition) right--，计算3的个数

  因此2和3一共有2*2种组合情况，然后再加上原来的结果即可。

  注意，我们可能会遇到一种特殊情况，[1,1,2,2,2,2]，即left和right的值是相同的。此时第一个while循环中，由于元素一直相同，因此最终left = right+1，导致left大于right，因此第二个while循环就不会进行。

  因此这个时候的排列组合计算公式 (left - tl)*(tr - right) = 0，结果会是错的。

  但我们观察发现，其实这个时候只要把 right - left 就能直接得到重复元素2的个数，就可以直接通过 排列组合计算公式得到答案。因此只需要多加一条判断，来计算这种情况即可。