刷算法(9)-较小的三数之和

259. 较小的三数之和(会员题)

给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。

输入: nums = [-2,0,1,3], target = 2
输出: 2 
解释: 因为一共有两个三元组满足累加和小于 2:
     [-2,0,1]
     [-2,0,3]

解法

public int threeSumSmaller(int[] nums, int target) {
        int result = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    result += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }

心得

读题

注意题目要求是返回的满足要求的i、j、k三元组个数，这意味着如果有两个数字是重复的，虽然数值一样但是索引位置不同，也认为是不同的结果。所以进到for循环后，不能有nums[i] == nums[i-1]的剪枝操作，如果剪枝了直接答案会不对。

条件控制

这道题的关键在result += right - left;，即针对某个left，如果找到一个right满足要求小于了target，则right右边的数字一定是小于target的，因此直接得到个数right - left，然后让left移位。