c++ short code O(n^2) time and O(1) space solution

• The algorithm asks to enumerate all triplets without duplicates, therefore it is always good to sort the array first. Then we enumerate (a, b, c) with a <= b <= c and c < a + b. To do this, we can try a and b as a double for loop, then to find the number of possible c, we can find the first element nums[idx] such that nums[idx] >= a + b. An ordinary way to do this is to use binary search as the array is already sorted. But we can do better if we observe that b is also in the increasing order to be enumerated. If we find idx such that nums[idx] >= a + b, then when we enumerate next possible b' >= b, we can start our pointer from idx to find the first element nums[idx'] > a + b'. The inner while loop iterate at most O(n) time during the inner for loop.

``````class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int count = 0;
for (int i=0; i<nums.size(); i++) {
int idx = i+2;
for (int j=i+1; j<nums.size() - 1; j++) {
if ((nums[i] > 0) && (nums[j] > 0)) {
while ((idx < nums.size()) && (nums[idx] < nums[i]+nums[j])) {
idx++;
}
count += idx - j - 1;
}
}
}
return count;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.