@@ -0,0 +1,2309 @@
+package array.n_sum;%0A%0Aimport java.util.Arrays;%0A%0Apublic class Q611ValidTriangleNumber %7B%0A%0A    //Difficulty: Medium%0A    //TAG: LinkedIn%0A    //TAG: array%0A%0A    /**%0A     * 611. Valid Triangle Number%0A     * Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.%0A     * Example 1:%0A     * Input: %5B2,2,3,4%5D%0A     * Output: 3%0A     * Explanation:%0A     * Valid combinations are:%0A     * 2,3,4 (using the first 2)%0A     * 2,3,4 (using the second 2)%0A     * 2,2,3%0A     * Note:%0A     * The length of the given array won't exceed 1000.%0A     * The integers in the given array are in the range of %5B0, 1000%5D.%0A     */%0A%0A    /*%0A    Solution 1:%0A    for i = 0 for j = i + 1 for k = len - 1 loop%0A    third loop until nums%5Bk%5D %3C nums%5Bi%5D + nums%5Bj%5D then all numbers are valid combinations, add k - j to res%0A%0A    Time: O(nlogn + n%5E3)%0A    Space: O(1)%0A     */%0A%0A    public int triangleNumber(int%5B%5D nums) %7B%0A        if (nums == null) return 0;%0A        Arrays.sort(nums);%0A        int count = 0;%0A        for (int i = 0; i %3C nums.length - 2; i++) %7B%0A            for (int j = i + 1; j %3C nums.length - 1; j++) %7B%0A                int k = nums.length - 1;%0A                while (k %3E j && nums%5Bk%5D %3E= nums%5Bi%5D + nums%5Bj%5D) k--;%0A                count += k - j;%0A            %7D%0A        %7D%0A        return count;%0A    %7D%0A%0A    /*%0A    Solution 2:%0A    Make the i loop as largest number, i to be the pivot, loop left right from 0 and i - 1 to mid%0A    nums%5Bl%5D + nums%5Br%5D %3E nums%5Bi%5D means valid combinations, res += r - l, and we move r--, due to all after l will be%0A    in these valid combinations (if l + r %3E i, then l + 1 + r %3E i) try smaller r%0A    otherwise if nums%5Bl%5D + nums%5Br%5D %3C= nums%5Bi%5D not valid, move l++, (if l + r %3C= i then l + r - 1 %3C= i)%0A%0A    Time: O(n%5E2)%0A    Space: O(1)%0A     */%0A%0A    public int triangleNumber2(int%5B%5D nums) %7B%0A        Arrays.sort(nums);%0A        int result = 0;%0A        for (int i = 2; i %3C nums.length; i++) %7B%0A            int left = 0, right = i - 1;%0A            while (left %3C right) %7B%0A                if (nums%5Bleft%5D + nums%5Bright%5D %3E nums%5Bi%5D) %7B%0A                    result += right - left;%0A                    right--;%0A                %7D%0A                else left++;%0A            %7D%0A        %7D%0A        return result;%0A    %7D%0A%0A%7D%0A

611. Valid Triangle Number