C++ two pointers 99.64% with comments


  • 0
    B
    class Solution {
    public:
        int triangleNumber(vector<int>& nums) {
            // solution, sort + two pointers, O(n^2) time, O(1) space
            sort(nums.begin(), nums.end());
            int n = nums.size();    // again need to remember let size() be int for the nums.size()-2 !!!!
            int res = 0;
            for(int a=0; a<n-2; ++a){ // nums[a] <= nums[b] <= nums[c]
                int b = a + 1, c = b + 1;
                while(c<=n){
                    if(b<c && (c==n || nums[a]+nums[b]<=nums[c])){ // now c is the one after the last valid c. c==nums.size() is to consider the case like [1, 1, 1, 1, 1, 1]
                        res += (c-1) - (b+1) + 1;   // the valid range of c is [b+1, c-1], inclusively
                        ++b;    // after nums[b] increased, the new valid range of c will not be less than [b+1, c-1]
                    }
                    else{
                        ++c;
                    }
                }
            }
            
            return res;
        }
    };

Log in to reply
 

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