Find the three number from the array that sum to a target number.

# Method 1 :

class FindTripletNumbersThatSumToTargetNumber
  def initialize
    p "Enter the size of array :"
    array_size = gets.strip.to_i
    if array_size < 3
      puts "Array size should be greater than 3"
    else
      array = []
      for i in (0..array_size-1)
          p "Enter #{i+1} element :"
          array[i] = gets.strip.to_i
      end
      p "Enter the target number :"
      target_number = gets.strip.to_i
      find_3_Numbers_that_sum_to_target_number(array, array_size, target_number)
    end
  end


  def find_3_Numbers_that_sum_to_target_number(array, array_size, target_number)
    for i in 0..array_size-3
      j = i+1
      for j in j..array_size-2
        k = j+1
        for k in k..array_size-1
          if array[i] + array[j] + array[k] == target_number
            puts "Triplet is : #{array[i]}, #{array[j]}, #{array[k]}"
            return true
          end
        end
      end
    end
    return false
  end
end
number = FindTripletNumbersThatSumToTargetNumber.new

This is not an optimized solution as it's time complexity is O(n^3).

# Method 2 :

class FindTripletNumbersThatSumToTargetNumber
  def initialize
    p "Enter the size of array :"
    array_size = gets.strip.to_i
    if array_size < 3
      puts "Array size should be greater than 3"
    else
      array = []
      for i in (0..array_size-1)
          p "Enter #{i+1} element :"
          array[i] = gets.strip.to_i
      end
      p "Enter the target number :"
      target_number = gets.strip.to_i
      merge_sort array
      find_3_Numbers_that_sum_to_target_number(array, array_size, target_number)
    end
  end

  def merge_sort(array)
  n = array.length
  if n > 1
  mid = n/2
  lefthalf = array[0..mid-1]
  righthalf = array[mid..n-1]
  merge_sort lefthalf
  merge_sort righthalf
  i = j = k = 0
  while i < lefthalf.length and j < righthalf.length
  if lefthalf[i] < righthalf[j]
  array[k] = lefthalf[i]
  i = i+1
  else
  array[k] = righthalf[j]
  j = j+1
  end
  k += 1
  end

  while i < lefthalf.length
  array[k] = lefthalf[i]
  i = i+1
  k = k+1
  end

  while j < righthalf.length
  array[k] = righthalf[j]
  j = j+1
  k = k+1
  end
  end
  end

  def find_3_Numbers_that_sum_to_target_number(array, array_size, target_number)
    for i in 0..array_size-2
      j = i+1
      k = array_size-1
      for j in j..array_size-2
        while j < k
          if array[i] + array[j] + array[k] == target_number
            puts "Triplet is : #{array[i]}, #{array[j]}, #{array[k]}"
            return true
          elsif
            array[i] + array[j] + array[k] < target_number
            j += 1
          elsif array[i] + array[j] + array[k] > target_number
            k += 1
          end
        end
      end
    end
    puts "Triplet doesn't exist"
    return false
  end
end
number = FindTripletNumbersThatSumToTargetNumber.new

In this method we reduced the time complexity from O(n^3)  to O(n^2) simply by sorting the array first. Now this is optimized solution compared to above.