这道题相当于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;
}
