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;
    }