求解数组中和小于目标值的三元组计数问题及代码疑问

一、count += right - left 的直觉推导 #

首先明确前提：双指针法必须基于排序后的数组，你的输入排序后为 [-1, 1, 2, 3, 4]，target=5。

核心思路是固定一个元素 z（比如第一个元素 -1），然后在剩余子数组中找两个元素 x 和 y，满足 x + y < target - z（这里 target - z = 6）。

当用双指针遍历子数组时：

• 左指针 left 从 z 的下一个位置开始，右指针 right 从数组末尾开始。
• 若 nums[left] + nums[right] < target - z，由于数组是升序的，nums[left] <= nums[left+1] <= ... <= nums[right]，那么 nums[left] 和 nums[left+1]、nums[left+2]……nums[right] 的组合，全部满足 x + y < target - z。
• 这些有效组合的数量正好是 right - left 个（比如 left=1、right=4 时，有效组合是 (1,2)、(1,3)、(1,4)，共 4-1=3 个）。
• 统计完当前 left 的所有有效组合后，右移 left，去探索下一个 left 的情况。

用你的输入举例：

• 固定 z=-1，left=1、right=4：1+4=5 <6，count +=3，此时count=3；left右移到2。
• left=2、right=4：2+4=6 不小于6，右移right到3。
• left=2、right=3：2+3=5 <6，count +=3-2=1，此时count=4，正好是正确结果。

二、你的代码错误分析 #

你的逻辑问题主要有两点：

1. 单次计数遗漏多组有效三元组：每次满足 x+y+z < target 时只给count加1，但实际上此时存在多个符合条件的三元组，你只统计了其中一个。
2. 指针移动逻辑错误：满足条件时右移右指针，导致左指针一直停留在初始位置，无法探索左指针右移后的有效组合（比如你漏掉的 [-1,2,3]，就是左指针移到2、右指针在3时的组合，你的代码根本没处理到这个场景）。

三、代码修正方法 #

1. 先对数组进行排序，这是双指针法的基础。
2. 遍历数组中的每个元素作为固定的 z，在 z 之后的子数组中用双指针：
   • 初始化 left = z+1，right = nums.length -1
   • 当 left < right 时：
     • 若 nums[z] + nums[left] + nums[right] < target：
       • 一次性统计当前 left 对应的所有有效组合：count += right - left
       • 右移 left，探索下一个左指针的情况
     • 否则：
       • 当前右指针的元素太大，左移 right 缩小和

修正后的Java代码示例：

import java.util.Arrays;

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;
        int n = nums.length;
        for (int z = 0; z < n - 2; z++) {
            int left = z + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[z] + nums[left] + nums[right];
                if (sum < target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-1,4,2,1,3};
        int target =5;
        System.out.println(sol.threeSumSmaller(nums, target)); // 输出4
    }
}

内容的提问来源于stack exchange，提问作者isilia