[LeetCode/Easy] 1. Two Sum

1. Input

1) int 배열 nums

2) int 변수 target

 

2. Output

1) nums[i] + nums[j] == target을 만족시키는 int 배열 {i, j}

 

3. Constraint

1) 2 <= nums.length <= 104

2) -109 <= nums[i] <= 109

3) -109 <= target <= 109

4) 유효한 답은 딱 1개뿐

 

4. Example

Input: nums = {2,7,11,15}, target = 9
Output: {0,1}
설명: nums[0] + nums[1] == 9이기 때문에 {0, 1} 반환

 

5. Code

1) 첫 코드(2022/05/30)

int len = nums.length;
int sum; // num[i] + num[j]
int[] result = {0,0};
if(len==2)
    return new int[] {0,1};
else{
    for(int i=0 ; i<len-1 ; i++){ // num[i]
        sum = nums[i];
        for(int j=i+1 ; j<len ; j++){ // num[j]
            sum += nums[j];
            if(sum == target){
                result[0] = i;
                result[1] = j;
                break;
            }
            sum -= nums[j];
        } // for j
    } // for i
}
return result;

  - 처음부터 찾아보면서 target을 찾는 방법

  - 직관적이지만 비효율적인 코드

 

2) 수정 코드(2022/08/08)

if(nums.length==2)
    return new int[] {0,1};
int[] result = {0,0};
for(int i=0 ; i<nums.length-1 ; i++){ // num[i]
    int x = target - nums[i];
    for(int j=i+1 ; j<nums.length ; j++){ // num[j]
        if(x == nums[j]){
            result[0] = i;
            result[1] = j;
            break;
        }
    } // for j
} // for i
 return result;

  - 1)보다 짧아진 실행 속도, 줄어든 메모리 사용량

  - 계산량을 줄여서 생긴 결과

  - 여전히 비효율적