LeetCode 2 - Two Sum II - Input array is sorted

tags: 每日一LeetCode爆肝又爆頭

Description

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Link

• https://leetcode.com/problems/two-sum/description/

Version 1.0 - qsort

/*
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
static int compare(void const*a, void const*b)
{
    return *(int*)a - *(int*)b; 
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{

    int i = 0;
    int value = 0 ;     
    int *found = NULL;
    int target_index = 0;
    
    for( i = 0; i < numsSize; i++){
        value = target - nums[i];
        found = bsearch(&value, nums, numsSize, sizeof(int), compare);
        target_index = found - nums;
        
        if(NULL != found && target_index != i){
            break;
        }
    }
    
    *returnSize = 2;
    int *ret = malloc(sizeof(int)* *returnSize);
    ret[0] = i + 1;
    ret[1] = target_index + 1;
  
    return ret;
}