Leetcode - 259. 较小的三数之和

class Solution {

    /**
     * 已知条件：数组nums和目标值target
     * 题目要求：计算使得i < j < k && nums[i] + nums[j] + nums[k] < target的三元组(i, j, k)的个数
     * 举例说明：nums = [-2, 0, 1, 3], target = 2; ret = 2
     */
    
    //本题和第15题（https://leetcode-cn.com/problems/3sum/）类似，用双指针的方式来解决
    public int threeSumSmaller(int[] nums, int target) {
        
        //先进行排序
        Arrays.sort(nums);
        
        //用于统计有多少个满足条件的三元组
        int count = 0;
        
        //每次for循环都固定住一个i的值
        for(int i = 0; i <= nums.length - 3; i++){
            
            //而j和k则作为左右指针
            int j = i + 1, k = nums.length - 1;
            while(j < k){

                //如果三数之和过大，则k左移（这里还有另一层含义：此时j也是固定住的）
                if(nums[i] + nums[j] + nums[k] >= target){
                    k--;
                
                //如果三数之和小于target，此时就找到了(k - j)个满足要求的三元组，然后j右移以指向下一个数
                //比如此时i, j, k分别为1, 2, 5，那么显然[(1, 2, 3), (1, 2, 4), (1, 2, 5)]都是满足要求的三元组
                //因此count自增3；并且j自增1，这样下次while循环将会判断三元组(1, 3, 5)是否满足要求
                } else{
                    count += k - j;
                    j++;
                }
            }
        }
        return count;
    }
}