12/25 每日C (兩數和)

1. Two Sum

Solved

Easy

Topics

Companies

Hint

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

 /**

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

 動態記憶體配置

 指標變數=(指標變數所指的資料型態 *) malloc(所需的記憶空間)

釋放

free(指標變數)

 

 */

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

   

    int x,y,i,j,sum;

    *returnSize=2;

    int *ptr =(int *)malloc(2*sizeof(int));

    for (i=0;i+1<numsSize;i++)

    {

        x=*(nums+i);

        for(j=i+1;j<numsSize;j++)

        {

            y=*(nums+j);

            sum = x+y;

           

           

            if (sum==target){

               

                *ptr=i;

                *(ptr+1)=j;

                return ptr;

            }

        }

       

    }

    free(ptr);

   

return NULL;

   

}