Lesson 6 question 3 Triangle

源地址

https://app.codility.com/programmers/lessons/6-sorting/triangle/

Triangle 三角形

给定一个含有N个整数的非空数组A,满足一下条件时我们说(P, Q, R) 是一个三角形

• 0 ≤ P < Q < R < N
• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

比如：

A[0] = 10    A[1] = 2    A[2] = 5
A[3] = 1     A[4] = 8    A[5] = 20
           

(0, 2, 4) 是一个三角形.

写一个函数

class Solution { 
   		public int solution(int[] A);
   	 }
           

给定一个含有N个整数的非空数组A,如果存在一个三角形就返回1,否则返回0.

比如：

A[0] = 10    A[1] = 2    A[2] = 5
A[3] = 1     A[4] = 8    A[5] = 20
           

函数应该返回1.

A[0] = 10    A[1] = 50    A[2] = 5
  A[3] = 1	
           

函数应该返回0.

假定：

• N是范围在 [0…100,000]的整数
• A中的每个元素都是范围在 [−2,147,483,648…2,147,483,647]的整数

第一步

先对数组升序排序,对于一个升序的数组来说,一下4个条件中满足1肯定就满足3,4.所以只需要判断是否满足条件2即可.

• 0 ≤ P < Q < R < N
• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

如果在判断时使用加法,有可能出现溢出的问题,所以使用 A[P] > A[R] - A[Q] 来进行判断 .

public int solution(int[] A) {
        int N = A.length;
        if (N > 2) {
            Arrays.sort(A);
            for (int i = 0; i < N - 2; i++) {
                if (A[i] <= 0)
                    continue;
                if (A[i] > A[i + 2] - A[i + 1])
                    return 1;
            }
        }
        return 0;
    }