双指针经典算法题实战解析：从原理到代码

注意初始化时不要让两指针相等，否则无法进入循环检测。

4. 盛最多水的容器 (Container With Most Water)

题目链接： LeetCode 11

暴力枚举需要 O(N²)，利用单调性可以将复杂度降为 O(N)。核心思想是对撞双指针：左右指针分别指向数组首尾。

面积由较短边决定。如果固定短边向内移动，高度不可能增加，面积只会减小或不变。因此，我们总是移动高度较小的那个指针，试图寻找更高的边来扩大面积。这样只需遍历一次即可找到最大值。

5. 有效三角形的个数 (Valid Triangle Number)

题目链接： LeetCode 611

构成三角形的条件是任意两边之和大于第三边。若数组已排序（a ≤ b ≤ c），只需验证 a + b > c 即可。

优化策略是先排序，然后固定最大边 c，用双指针 left 和 right 在剩余部分查找满足条件的组合。若 nums[left] + nums[right] > nums[c]，说明 left 到 right-1 之间的所有数与 right 都能组成三角形，直接累加计数，然后 right--；否则 left++。

6. 两数之和 II (Two Sum II)

题目链接： LeetCode 167

输入数组已排序，直接使用对撞双指针。左指针指向头，右指针指向尾，根据当前和与目标值的比较移动指针：和大则右移左指针，和小则右移右指针，相等则返回结果。时间复杂度 O(N)。

7. 三数之和 (3Sum)

题目链接： LeetCode 15

这是双指针的经典进阶应用。外层循环固定一个数 i，内层使用双指针寻找另外两个数。难点在于去重和边界处理。

1. 去重： 如果 nums[i] 与前一个相同，跳过；找到一组解后，left 和 right 也要跳过重复值，避免重复三元组。
2. 边界： 确保 left < right，防止越界。

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i-1]: continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                res.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]: left += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0: left += 1
            else: right -= 1
    return res

8. 四数之和 (4Sum)

题目链接： LeetCode 18

在三数之和的基础上多套一层循环。同样需要注意去重逻辑和溢出问题。由于四个数相加可能超出整型范围，求和时需强转为长整型（如 C++ 中的 long long）。

以上这些题目展示了双指针在不同场景下的变体：同向移动、对撞移动、快慢指针等。掌握其背后的单调性与空间划分思想，比死记硬背代码更重要。