# 259 - 3Sum Smaller

解法一 - Two Pointer

這題跟 #16 很像，要注意的有兩點：

1. 這題是問 index triplets，所以不用特別排除 value 一樣的 nums[i] 起點，只要確保 index triplet 不會重複用到就好。

2. 當遇到 nums[l]+nums[r]<target 時，可以直接把 count += r-l，因為在這之中的所有組合 sum 一定也都比 target 小，不這樣寫的話會很難寫 while loop 裡的邏輯

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        int n=nums.size();
        int count=0;
        for(int i=0; i<n-2; i++) {
            int l=i+1, r=n-1;

            while(l<r) {
                int sum = nums[i]+nums[l]+nums[r];

                if(sum < target) {
                    // since nums[r] >= nums[l]
                    // we can replace nums[r] by any number between
                    // l and r to get a sum less than the target sum
                    count += r-l;
                    l++;
                }
                else 
                    r--;
            }
        }

        return count;
    }
};