[LeetCode] 167. Two Sum II - Input Array Is Sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/?envType=study-plan-v2&envId=top-interview-150 

Two Sum II - Input Array Is Sorted - LeetCode

문제 유형 : 투 포인터

문제 난이도 : Medium

 

 

문제

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가 주어집니다. 중복이 있는 오름차순으로 정렬이 되어 있습니다.

더해서 정해진 값 target을 만들수 있는 두 수의 인덱스를 반환하시오.

단 하나만의 값만 나오게 되어있습니다.

상수 공간 복잡도를 사용하시오. (O(1))

 

풀이

투 포인터를 이용하여 문제를 해결한다.

배열의 왼쪽 끝을 left, 오른쪽 끝을 right로 변수를 만들어서,

왼쪽이 오른쪽보다 커지기 전까지 다음을 반복한다:

    두 수의 합 sum이 target과 같으면: (처음은 가장 작은값과 가장 큰값의 합으로 시작)

        두 인덱스를 반환한다.

    두 수의 합 sum이 target보다 작으면:

        수를 더 키워야 하므로 left를 1 키운다.

    두 수의 합 sum이 target보다 크면:

        수를 더 줄여야 하므로 right를 1 줄인다.

 

 

코드

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        
        while (left < right) {
            const int sum = numbers[left] + numbers[right];
            
            if (sum == target) {
                return {left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return {};
    }
};

 

Python3

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while left < right:
            sum = numbers[left] + numbers[right]
            if sum == target:
                return [left+1, right+1]
            elif sum < target:
                left += 1
            else:
                right -= 1
        
        return []

 

Dart

class Solution {
  List<int> twoSum(List<int> numbers, int target) {
    int left = 0, right = numbers.length - 1;

    while(left < right) {
      int sum = numbers[left] + numbers[right];

      if(sum == target) {
        return [left + 1, right + 1];
      } else if(sum < target) {
        left++;
      } else{
        right--;
      }
    }
    return [];
  }
}

 

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;

        while(left < right) {
            int sum = numbers[left] + numbers[right];

            if(sum == target) {
                return new int[] {left + 1, right + 1};
            } else if(sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[] {};
    }
}

 

swift

class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        var left = 0, right = numbers.count - 1

        while left < right {
            let sum = numbers[left] + numbers[right]

            if sum == target {
                return [left + 1, right + 1]
            } else if sum < target {
                left += 1;
            } else {
                right -= 1;
            }
        }
        return []
    }
}