Pair in array with target sum

Given a number target and an array of numbers nums find the index of numbers which has sum equal to target.

Algorithm is:

  1. Iterate over the array
  2. subtract the first element from target, find the difference in the array
  3. Get index of current element and difference if found within the array.

c++ solution

#include <algorithm> // for std::distance and std::find
#include <vector>

std::vector<int> two_sum(std::vector<int>& nums, int target) {
  std::ptrdiff_t first_idx = 0, second_idx = 0;
  for(size_t i = 0; i <= nums.size(); i++){
    int difference = target - nums[i];
    second_idx = std::distance(nums.begin(), std::find(nums.begin()+i+1,
     nums.end(), difference));
     if(second_idx < nums.size()){
       first_idx = i;
        break;
      }
   }
   return {static_cast<int>(first_idx), static_cast<int>(second_idx)};
 }

Ruby solution

def two_sums(nums, target)
  first_idx, second_idx = 0, 0
  nums.each_with_index do |num, idx|
    difference = target - num
    second_idx = nums.rindex(difference)
    first_idx = idx unless second_idx.nil?
    break
  end
  [first_idx, second_idx]
end

Author: Saurabh Purnaye

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s