Given an integer array nums, return 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: nums = [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

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Solution

• for 문을 세 번 중첩하는 방법을 생각하는 것은 쉽지만,

  시간복잡도 O(n^3) 이므로 매우 비효율적입니다.

• 아래는 leetcode에 단 하나 있는 rust solution 인데, 효율성이 매우 아쉽습니다.

impl Solution {
    pub fn triangle_number(nums: Vec<i32>) -> i32 {
				// nums 각 원소에 대해 양수인지 확인하고, 양수인 원소만 필터링하여
				// 새로운 가변 벡터 nums 에 저장한다.( <= 정렬을 하기 위한 사전 준비)
        let mut nums = nums.iter().filter(|&n| *n > 0).collect::<Vec<_>>();
        if nums.len() < 3 {
            return 0;
        }

				// 정렬
        nums.sort_unstable();

        let mut answer = 0;
        **for** i in 0..nums.len() - 2 {
            // let mut k = i + 2;
            **for** j in i + 1..nums.len() - 1 {
								let mut k = j + 1;
								// 삼각형이 성립하지 않을 때까지만 반복함으로써
								// 약간의 효율성 고려
                **while** k < nums.len() && nums[i] + nums[j] > *nums[k] {
                    k += 1;
                }
								// 현재 선택한 i 와 j 에 대해 형성 가능한 삼각형의 갯수
                answer += k - j - 1;
            }
        }
        answer as i32
    }
}

• 조금 더 효율적으로 해결하기 위해 sliding window 방식의 ‘Two pointer algorithm’ 을 사용해보면 어떨까 생각했습니다.

  시간복잡도는 O(n^2) 으로 지수의 성격상 속도가 획기적으로 증가합니다.

  1. nums를 오름차순 정렬합니다.
  2. 삼각형이 성립하려면 가장 큰 변의 길이가 나머지 두 변의 길이의 합보다 작아야 합니다. 따라서 가장 큰 변의 길이(nums의 마지막 원소부터 반대 방향)를 기준으로 합니다. 가장 큰 변을 C 라고 가정하고 해당값의 index 를 c 라고 가정합니다. index c 는 가장 큰 수인 마지막 원소부터 index 2 까지 순차적으로 작아집니다.
     1. 이제 가장 작은 변 A와 나머지 변 B 의 인덱스는 0 ≤ index < c 입니다. index 범위 안에서 삼각형이 성립하는 경우를 구합니다.
     2. value a 는 value b 보다 항상 작아야 합니다.(전제)
        1. value a + value b > value c ⇒ index b 를 1 감소시키고, count 를 1 증가시킵니다.
        2. value a + value b ≤ value c ⇒ 삼각형이 성립하지 않으므로 가장 작은 a 를 1 증가시킵니다.
  3. count 를 반환합니다.

  impl Solution {
      pub fn triangle_number(nums: Vec<i32>) -> i32 {
          if nums.len() < 3 {
              return 0;
          }
  
          let mut nums = nums;
          nums.sort();
  
          let mut count = 0;
          let n = nums.len();
  
          **for** c_index in (2..n).rev() {
              let mut a_index = 0;
              let mut b_index = c_index - 1;
  
              **while** a_index < b_index {
                  if nums[a_index] + nums[b_index] > nums[c_index] {
                      count += (b_index - a_index) as i32;
                      b_index -= 1;
                  } else {
                      a_index += 1;
                  }
              }
          }
          
          count
      }
  }
  

• 처음부터 역순으로 정렬하여, rev() 를 없애면 가장 빠른 속도로 올라갈 듯 합니다.