[Leetcode] 1. Two Sum

Identifying the Problem

nums 정수 배열 안의 두 수의 합이 target과 같다면, 해당 두 수의 index를 정수 배열 형태로 리턴한다.예를 들어 nums = [2,7,11,15], target = 9 라면, 리턴 값은 [0,1]이 된다.

 

제약 조건은 다음과 같다.

• 2 <= 정수 배열 길이 <= 10^4
• -10^9 <= 배열 안의 요소 값 <= 10^9
• -10^9 <= target <= 10^9 

 

Organizing thoughts

제약조건은 int 범위를 만족하므로 따로 long int 를 사용하지 않았다.

 

0. 정답 배열을 선언하고, 동적할당을 한다.

1. 중첩 반복문을 사용해 0번 + 1번, 0번 + 2번 .... numsSize-2번 + numsSize-1번의 값을 구한다.

1-1 중첩 반복시 n번은 n+1번부터 비교한다.

2. target과 동일할 시 해당 index 둘을 정답 배열에 넣고, 반복을 중단한다. 

3. 결과를 return 한다.

 

Sourcecode

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    int * answer = malloc(sizeof(int)*8); //0번 
    *returnSize = 2;
    
    
    for(int i=0; i<numsSize - 1; i++) //1번 nums[numsSize]는 메모리 초과이므로 끝에서 두번째까지만
        for(int j=i+1; j<numsSize; j++)
            if(nums[i]+nums[j] ==target) //2번 
            {
            	*(answer) = i;
                *(answer+1) = j;
             	break;
            }
            
    return answer; //3번
}

 

Mistake

for(int j=i+1; j<numsSize; j++ ) 에서 j=i+1 부분을 j=0부터 시작해 중복해서 

nums[0] 과 nums[0] 을 더하는 실수를 했다.

 

New things learned

int 의 범위 : –2,147,483,648 ~ 2,147,483,647

동적할당 : int* nums = malloc(sizeof(int) * 길이) -> 이후 free(nums)

배열길이 구하기 : len = sizeof(arr) / sizeof(int)