博文中会简要介绍Leetcode P0259题目分析及解题思路。

“3Sum Smaller”是一道中等难度的题目，依据题目要求，我们可以利用双指针的想法来解答这道题。

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Follow up: Could you solve it in O(n2) runtime?

首先由于这道题并没有询问具体的下标，而仅仅是要求统计个数，所以首先我们可以先对给定的数组进行排序，这样我们可以利用排序后的数组特性（即从小到大）来应用双指针的思路。

其次我们不难发现，这道题由于有三个量i、j和k，所以实际上有三个指针，但是一般求解多指针问题，我们尽量要将它化归为双指针问题，所以我们可以每次固定一个指针，比如i，然后移动其他两个指针。

对于其他两个指针j和k，我们令它们从两端出发，先将k由数组末端向j移动，由于数组是有序的，所以如果满足了nums[j] + nums[k] < target - nums[i]这个条件，此时我们应当有任意的(j, k]之间的坐标m都可以满足nums[j] + nums[m] < target - nums[i]，于是我们可以得到此时i和j固定在当前位置的情况下，可以满足条件的组合个数。然后我们再将j向k移动，由于数组有序，所以nums[j] < nums[j+1]，所以k至少要在当前位置才有满足条件的可能，否则必须将k向j移动，于是我们无需重置k的位置。以此类推，即可得到时间复杂度为O(n^2)的双指针解法。

以下是Java的题解代码实现。

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int N = nums.length, count = 0;
        if (N < 3) {
            return count;
        }
        
        Arrays.sort(nums);
        
        for (int i=0; i<N-2; ++i) {
            int j = i+1, k = N-1, aim = target-nums[i];
            while (j < k) {
                int sum = nums[j]+nums[k];
                if (sum < aim) {
                    count += (k-j);
                    ++j;
                }
                else {
                    --k;
                }
            }
        }
        
        return count;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int N = nums.size(), count = 0;
        if (N < 3) {
            return count;
        }
        
        sort(nums.begin(), nums.end());
        for (int i=0; i<N-2; ++i) {
            int j = i+1, k = N-1, aim = target-nums[i];
            while (j < k) {
                int sum = nums[j]+nums[k];
                if (sum < aim) {
                    count += (k-j);
                    ++j;
                }
                else {
                    --k;
                }
            }
        }
        
        return count;
    }
};