Triangle Count (Lintcode 382)

这道题相当于two sum 以及 two sum II 的follow up题。是two pointer类题目。而这道题的要点是。两个pointer均要在 i 的左边。这跟three sum有着方式上的区别。

所以要记住这样的方法。当two pointer在 i 的右边讨论不出来时，想想把他们放到 i 的左边。

int triangleCount(vector<int> &S) {
        // write your code here
        if(S.size() < 3) return 0;
        sort(S.begin(), S.end());
        int cnt = 0;
        for(int i=2; i<S.size(); i++){
            int left = 0, right = i-1;
            while(left < right){
                if(S[left] + S[right] > S[i]){
                    cnt += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return cnt;
    }