LeetCode-[수조]-유효 삼각형 의 개수

마이너스 정 수 를 포함 하지 않 는 배열 을 지정 합 니 다.삼각형 세 변 을 구성 할 수 있 는 3 원 조 의 개 수 를 통계 하 는 것 이 임무 입 니 다.
예시 1:

  : [2,2,3,4]
  : 3
  :
      : 
2,3,4 (      2)
2,3,4 (      2)
2,2,3

주의:
4.567917.배열 의 길 이 는 1000 을 초과 하지 않 는 다
4.567917.배열 안의 정수 범 위 는[0,1000]이다
문제 풀이:삼각형 을 구성 하려 면 삼각형 중 두 개의 가장 짧 은 변 의 합 이 가장 긴 변 보다 크 면 된다. 이러한 원 리 를 바탕 으로 우 리 는 먼저 배열 을 작은 것 부터 큰 것 까지 정렬 할 수 있다.배열 을 정렬 한 후에 우 리 는 이렇게 생각 하고 특정한 수 를 고정 시 킨 다음 에 좌우 두 개의 지침 으로 각각 특정한 수 를 가리 킬 수 있다.좌우 지침 이 가리 키 는 숫자의 합 이 우리 가 고정 한 수 보다 크 면 이런 상황 이 성립 된다 는 것 을 설명 할 수 있다.그리고 오른쪽 바늘 을 왼쪽으로 한 명 이동 시 켜 만족 하지 않 을 때 까지 계속 판단 하고 왼쪽 바늘 을 오른쪽으로 한 명 이동 시 켜 계속 판단 한다.왼쪽 바늘 이 오른쪽 바늘 과 겹 칠 때 까지.이 사고 에 따라 우 리 는 배열 을 큰 것 에서 작은 것 으로 옮 겨 다 니 며 현재 옮 겨 다 니 는 숫자 nums[i]를 고정 시 키 고 왼쪽 포인터 가 0 번 째 숫자 nums[0]를 가리 키 며 오른쪽 포인터 가 이 수의 왼쪽 숫자 nums[i-1]를 가리 키 도록 합 니 다.nums[left]+nums[right]>nums[i]를 사용 할 때 오른쪽 포인터 right 를 고정 시 키 면 왼쪽 포인터 left 가 오른쪽 으로 지나 갈 때 왼쪽 포인터 와 오른쪽 포인터 사이 의 것 도 요 구 를 만족 시 킬 것 이 라 고 생각 할 수 있 습 니 다.그래서 count+=(right-left)이 있 습 니 다. 오른쪽 포인터 right 를 왼쪽으로 한 자 리 를 옮 겨 판단 을 계속 하고 성립 되면 right 는 앞에서 조작 을 계속 반복 합 니 다.만약 성립 되 지 않 는 다 면 두 수의 합 이 너무 작 다 는 것 을 설명 합 니 다.이때 왼쪽 포인터 left 를 오른쪽으로 한 자 리 를 옮 기 고 판단 을 계속 합 니 다.left 와 right 포인터 가 겹 칠 때 까지 nums[i]의 모든 상황 을 고려 했 습 니 다.마지막 에 배열 이 다 옮 겨 다 니 고 결과 가 나 왔 습 니 다.

class Solution {
    public int triangleNumber(int[] nums) {
        int n=nums.length;
        int res=0;
        Arrays.sort(nums);
        for(int i=n-1;i>=2;i--){
            int l=0,r=i-1;
            while(lnums[i]){
                    res+=(r-l);
                    r--;
                }else{
                    l++;
                }
            }
        }
        return res;
    }
}