Easier to understand solution based on the O(n^2) editorial solution


  • 0
    E
    1. move check nums[i] == 0 to the first loop
    2. use i,j=i+1,k=j+1
    public class Solution {
        public int TriangleNumber(int[] nums) {
            Array.Sort(nums);
            int n = nums.Length, count = 0;
            
            for(int i=0; i<n-2;i++){
                if(nums[i] == 0) continue;
                for(int j=i+1; j<n-1;j++){
                    int k=j+1;
                    while(k<n && nums[i]+nums[j]>nums[k]) k++;
                    count+= k - j - 1; // k is in the first invalid position. 
                }
            }
            
            return count;
        }
    }
    

Log in to reply
 

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