259. 3Sum Smaller

做题历程：

1. 本题应该做了不止一次了，本次独立解出，大概耗时10分钟

本题难度还可以，算是顺利解出了，说下大体思路：

1. 对给定数组进行sort()，这样不会影响时间复杂度，目前只是O(nlogn)
2. 选定其中一个元素：我选的是3个数中处于中间的元素，外层循环是以这个元素从1到length() - 1遍历
3. 内层循环是关键点，搞两个pointers分别代表最小的元素和最大的元素，往中间遍历
   1. 将3个数相加，如果小于target，则从最大元素到中间元素的所有数都可以作为最大元素，此时将最小元素往后弄一位，进入下一个循环的比价
   2. 如果3个数相加小于target，将最大的元素往中间移一位，在中间元素不变的情况下，后面的元素再也用不到了
4. 本题的难点就是要理解内层循环看似复杂，其实本质上就是左右两个pointers分别往里面扫描，复杂度就是O(n)
5. 所以整个题的时间复杂度是O(n^2) + O(nlogn) = O(n^2)

代码如下：

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        if (nums.size() < 3) {
            return 0;
        }
        int cnt = 0;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size() - 1; ++i) {
            int left = 0;
            int right = nums.size() - 1;
            while (left < i && i < right) {
                if (nums[left] + nums[i] + nums[right] < target) {
                    ++left;
                    cnt += (right - i);
                }
                else {
                   --right; 
                }
            }
        }
        return cnt;
    }
};