[1] Two Sum

© Jarvus Chen / www.jarvus.net

Description

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

Hint: The returned array must be malloced, assume caller calls free().

Required knowledge

You have to familiar with memory allocate to use array as function parameters and return values. These information can be searched by these keywords in Google.

• malloc and free
• new and delete

Or, my previous note: http://jarvus.dragonbeef.net/note/noteArduinoFunc.php

My solution

In C language, the only one way to pass array is use pointer. nums is input array with full data which length is numsSize. target is the sum value of two numbers.

• Declare a array with 8 bytes ( 1 int is in 4 bytes), because we need to return 2 int as results

• Use 2 loop to scan all numbers and prevent repeating the same numbers. For example,

  • If nums has 4 values which means nums[4]
  • In the first round, keep nums[0] and test nums[1], nums[2] and nums[3]
  • In the second round, keep nums[1] and test nums[2] and nums[3]
  • In the third round, keep nums[2] and test nums[3]

• Save two index in ans

• Because of the hint, we don't have to free(ans). It will be called free by caller on its return variable

int* twoSum(int* nums, int numsSize, int target) {
    int* ans = malloc(sizeof(int)*2);
    for ( int i = 0 ; i < numsSize ; i++){
        for ( int j = 0; j < numsSize ; j++){
            if ( i < j ){
                if ( (nums[i] + nums[j]) == target){
                    ans[0] = i;
                    ans[1] = j;
                }
            }
        }
    }
    return ans;
}

Others solution

There are some solutions by the hash table method. I thought that is not a easier way for beginner, so I won't mention it. Following method is a little smart way to prevent repeated number.

int* twoSum(int* nums, int numsSize, int target) {
    int* ans = malloc(sizeof(int)*2);
    for ( int i = 0 ; i < numsSize ; i++){
        for ( int j = i + 1; j < numsSize ; j++){
            if ( (nums[i] + nums[j]) == target){
                    ans[0] = i;
                    ans[1] = j;
            }
        }
    }
    return ans;
}