跨越美利坚面试创业技术培训 2018-05-30
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.
Example 1:
Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3
Note:
reference --https://leetcode.com/problems/valid-triangle-number/solution/
Idea: it is not like permutation problem(for each position, there are many cases to fill in), because we choose some elements from the array.
sort: to check only one case a+b >c instead of three of them
a +b > c and sorting the array
accepted solution 1: binary search
class Solution { int res = 0; public int binarySearch(int[] nums, int left, int right, int target){//[] while(right >= left && right < nums.length ){//stop comdition is right >= left: there is onl one element int mid = (right - left)/2 + left; if(nums[mid] >= target){ right = mid -1; }else { left = mid + 1; } } return left;// it is on the right of the number we want: real target, left(index) } public int triangleNumber(int[] nums) { Arrays.sort(nums); int n = nums.length; for(int i = 0 ; i <= n-3 ; i++){ int a = nums[i]; for(int j = i+1 ; j <= n-2 ; j++){ int b = nums[j]; //System.out.println(j+1); int index = binarySearch(nums,j+1,n-1, a+b ); //[]// find the largest element smaller than a+b //System.out.println(index); //System.out.println(nums[index]); res = res + index - j-1; //why - 1?? } } return res; } }
Accepted solution 2 -- O(n^2)
class Solution { public int triangleNumber(int[] nums) { int res = 0; //int n = nums.length; Arrays.sort(nums); for(int i = 0; i < nums.length-2; i++){ if(nums[i] == 0) continue; int k = i + 2; // why here if(nums[k] == 0) continue; for(int j = i+1 ; j<nums.length-1; j++){ if(nums[j] == 0) continue; while(k < nums.length && nums[k]< nums[i]+nums[j] && nums[k]!=0){ k++;// move k } res = res + k - j -1; } } return res; } }
traverse k and j only n^2 -> square time complexixity