Two Sum

|問題説明|

vector<int>& nums
 int target

vector<int>

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

||トラブルシューティング|

vector<int> answer;

- 모든 nums를 돌면서 nums[i] + nums[j] == target일때 answer에 i, j를 저장하고 break
- return answer; 

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

|コード|

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;
    }
};

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;
    }
};

- 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;
    }
};

- 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;
    }
};