Two Sum

yyeahh·2020년 9월 29일
0

LeetCode

목록 보기
2/9

|| 문제설명 ||

  1. 정수형 배열 nums에서 두 숫자를 골라 target을 만들고 해당하는 숫자의 위치들을 return
  2. 하나의 정답만이 존재하고, 같은 원소를 쓸 수 없다.
  • Input

    vector<int>& nums
     int target
  • Output

    vector<int>
  • 제한사항

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

|| 문제해결과정 ||

vector<int> answer;
1) O(n^2) : 중복 for문
- 모든 nums를 돌면서 nums[i] + nums[j] == target일때 answer에 i, j를 저장하고 break
- return answer; 
2) O(n) : 해시 사용
- map<int, int> m : m[숫자] = 위치
- for문을 통해 nums의 모든 요소들을 m에 추가 시키고 만약 중복되는 값이 있다면 해당값*2 == target인지 확인하고 answer에 값 추가
- 나머지는 nums를 돌면서 (target - nums[i]) 가 존재하는지 확인하면서 존재할때 해당 위치들을 answer에 추가

|| 코드 ||

[2020.09.29] 성공

- O(n^2)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> answer;
        for(int i = 0; i < nums.size() - 1; i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(nums[i] + nums [j] == target) {
                    answer.push_back(i);
                    answer.push_back(j);
                    break;
                }
            }
        }
        return answer;
    }
};


[2020.09.29] 실패
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> answer;
        map<int, int> m;
        for(int i = 0; i < nums.size(); i++) {
            if(m[nums[i]]) {
                if(nums[i] * 2 == target) {
                    answer.push_back(m[nums[i]]);
                    answer.push_back(i);
                    break;
                }
                else continue;
            }
            m[nums[i]] = i;
        }
        if(!answer.empty()) return answer;

        for(int i = 0; nums[i] <= target; i++) {
            if(m[target-nums[i]]) {
                answer.push_back(m[nums[i]]);
                answer.push_back(m[target-nums[i]]);
                break;
            }
        }
        return answer;
    }
};

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

같은 숫자가 등장할 때의 if문이 작동x,
앞 숫자의 위치가 0이기에 작동 x

[2020.09.29] 실패
- map에 저장하는 (위치)를 (위치+1)로 저장하여 if문에 걸리지 않게함.
- 나중에 answer에 추가할때 (값-1)으로 바꿔준다.
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> answer;
        map<int, int> m;
        for(int i = 0; i < nums.size(); i++) {
            if(m[nums[i]]) {
                if(nums[i] * 2 == target) {
                    answer.push_back(m[nums[i]] - 1);
                    answer.push_back(i);
                    return answer;
                }
                else continue;
            }
            m[nums[i]] = i + 1;
        }
        for(int i = 0; nums[i] <= target; i++) {
            if(m[target-nums[i]]) {
                answer.push_back(m[nums[i]] - 1);
                answer.push_back(m[target-nums[i]] - 1);
                break;
            }
        }
        return answer;
    }
};

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

3이 하나밖에 없기 때문에 6-3=3인 경우를 예외로 처리해줘야한다.

[2020.09.29] 성공
- if(target-nums[i] == nums[i]) continue; 를 추가해 해당 경우를 건너뛰게 한다.
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> answer;
        map<int, int> m;
        for(int i = 0; i < nums.size(); i++) {
            if(m[nums[i]]) {
                if(nums[i] * 2 == target) {
                    answer.push_back(m[nums[i]] - 1);
                    answer.push_back(i);
                    return answer;
                }
                else continue;
            }
            m[nums[i]] = i + 1;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(m[target-nums[i]]) {
                if(target-nums[i] == nums[i]) continue;
                answer.push_back(m[nums[i]] - 1);
                answer.push_back(m[target-nums[i]] - 1);
                break;
            }
        }
        return answer;
    }
};


1) 평가


2) 속도&메모리

0개의 댓글