C++ 15ms solution (beats 100%) (with Python version)


  • 0
    S

    C++

    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int result = 0;
        for (int i = 0; i + 2 < nums.size(); i++) {
            if (nums[i] == 0)
                continue;
            int k = nums.size() - 1;
            for (int j = nums.size() - 2; j > i; j--) {
                for (; k > j && nums[k] >= nums[i] + nums[j]; k--) {}
                result += (k - j);
            }
        }
        return result;
    }
    

    Python

    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = sorted(nums)
        result = 0;
        for i in range(len(nums) - 2):
            if (nums[i] == 0):
                continue;
            k = len(nums) - 1;
            for j in range(len(nums) - 2, i, -1):
                while (k > j and nums[k] >= nums[i] + nums[j]):
                    k -= 1
                result += (k - j);
        return result;
    

Log in to reply
 

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