https://leetcode.com/problems/3sum-smaller/description/
image.png
这道题，暴力解法n^3,遍历所有可能，如果小于TAR，就CNT++；
followup : n^2
这样肯定不能一个个加了。得一次批量加起来。
为了达到这个效果，我们必须先固定一个指针，剩下的2个一个放在最左段，一个放在尽可能靠右。这时3个加起来，如果<target,如果数组是排好序的，那么中间那个指针，往左移移到最左边，这些全部都是满足条件的。
这样就用了O1的时间，代替了ON 的操作。
如果>target，意味，最小的这个数已经和2个最大的组合，还不满足条件，那么最小的这个数一定不存在解。这样我们就可以放心的右移最左的指针。然后重复上述的比较。
public int threeSumSmaller(int[] ids, int tar) {
Arrays.sort(ids);
int l = ids.length;
int cnt = 0;
for(int i = l - 1; i >= 2; i--){
int cur = ids[i];
int j = 0, k = i-1;
while(j<k){
if(ids[j]+ids[k]+cur<tar){
cnt+=(k-j);
j++;
}else{
k--;
}
}
}
return cnt;
}
