167. Two Sum II - Input Array Is Sorted

mmmYoung·2022년 3월 14일
0

리트코드

목록 보기
11/21

문제 설명

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.

이미 감소하지 않는 순서로 정렬된 인덱스 시작값이 1인 정수형 배열 numbers가 주어진다.
두 원소를 더했을 때 타겟 값이 되는 두 수의 인덱스를 찾아라.
이 두 수를 numbers[index1],numbers[index2]라고 할때, 1<=index1<index2<=numbers.length 이다.

  • 같은 원소를 중복하여 사용할 수 없다.
  • 고정 공간을 이용하여라.
  • 답은 반드시 하나이다.

출력 예시

접근 방법

첫번째 시도

이미 정렬 된 배열이므로, start와 end를 이용하여 그 합이 타겟 값과 같은 지 확인하기.

소스코드

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> answer;
        int start = 0;
        int end = numbers.size()-1;
        while(start <= end){
            if(numbers[start]+numbers[end] > target) end--;
            else if(numbers[start]+numbers[end] < target) start++;
            else {
                answer.push_back(start+1);
                answer.push_back(end+1);
                break;
            }
            
        }
        
        return answer;
    }
};

돌아보기

vector <int> answer;
answer.push_back(1);
answer.push_back(2);
return answer;

=

return {1,2};

바로 출력 할 수 있는 벡터는 아래처럼 간소화하여 출력하기!

profile
안냐세여

0개의 댓글