LinkedIn: Find all Triangles in an array

/**
 * Find threevalues that can be the lengths of the sides of a triangle.
 * Three segmentsof lengths A, B, C can form a triangle if and only if:
 *
 *      A + B > C
 *      B + C > A
 *      A + C > B
 *
 * e.g.
 *  6, 4, 5 can form a triangle
 * 10, 2, 7 can't
 *
 * @paramsegmentLengths the lengths of segments that might form a triangle.
 * @return threevalues that can be the lengths of the sides of a triangle,
 *         or an empty array if there are no suchvalues in segmentLengths.
 * sample input:segmentLengths = [10, 5, 7, 4, 3]

 */

Discussion

先排序，给定i和j，找满足A[i] + A[j] > A[k]的所有k。 Sort the input first. Then iterate A[i], and A[j], and check if A[i] + A[j] > A[k]. If yes, add into the result. We don't have to test the other two because if the sum of the two short edges is greater than the long edge, then the condition automatically holds.

Solution 1 Brute force

public class Triangle {
    public List<List<Integer>> validTriangle(int[] edges) {
        List<List<Integer>> result = new ArrayList<>();
        if (edge == null || edges.length < 3) {
            return result;
        }

        Arrays.sort(edges);

        for (int i = 0; i < edges.length - 2; i++) {
            for (int j = i + 1; j < edges.length - 1; j++) {
                for (int k = j + 1; k < edges.length; k++) {
                    if (edges[i] + edges[j] > edges[k]) {
                        List<Integer> curr = new ArrayList<>();
                        curr.add(edges[i]);
                        curr.add(edges[j]);
                        curr.add(edges[k]);
                        result.add(curr);
                    }
                }
            }
        }

        return result;
    }
}

Solution 2

不用找没一个k，可以找到最后一个满足条件的k，然后下次就从下一个开始了。 Time Complexity: O(n^2). The time complexity looks more because of 3 nested loops. If we take a closer look at the algorithm, we observe that k is initialized only once in the outermost loop. The innermost loop executes at most O(n) time for every iteration of outer most loop, because k starts from i+2 and goes upto n for all values of j. Therefore, the time complexity is O(n^2).

int comp(const void* a, const void* b)
{  return *(int*)a > *(int*)b ; }

// Function to count all possible triangles with arr[] 
// elements
int findNumberOfTriangles(int arr[], int n)
{
    // Sort the array elements in non-decreasing order
    qsort(arr, n, sizeof( arr[0] ), comp);

    // Initialize count of triangles
    int count = 0;

    // Fix the first element.  We need to run till n-3
    // as the other two elements are selected from 
    // arr[i+1...n-1]
    for (int i = 0; i < n-2; ++i)
    {
        // Initialize index of the rightmost third 
        // element
        int k = i+2;

        // Fix the second element
        for (int j = i+1; j < n; ++j)
        {
            // Find the rightmost element which is
            // smaller than the sum of two fixed elements
            // The important thing to note here is, we 
            // use the previous  value of k. If value of 
            // arr[i] + arr[j-1] was greater than arr[k],
            // then arr[i] + arr[j] must be greater than k, 
            // because the array is sorted.
            while (k < n && arr[i] + arr[j] > arr[k])
               ++k;

            // Total number of possible triangles that can 
            // be formed with the two fixed elements is
            //  k - j - 1.  The two fixed elements are arr[i]
            // and arr[j].  All elements between arr[j+1]/ to 
            // arr[k-1] can form a triangle with arr[i] and arr[j].
            // One is subtracted from k because k is incremented 
            // one extra in above while loop.
            // k will always be greater than j. If j becomes equal
            // to k, then above loop will increment k, because arr[k]
            //  + arr[i] is always greater than arr[k]
            count += k - j - 1;
        }
    }

    return count;
}