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

orca·2023년 8월 28일
0

problem

목록 보기
10/28

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

개요

  1. 오름차순 정렬된 배열 numbers가 주어진다.
  2. numbers[index1] + numbers[index2] = target 인 index1과 index2를 찾아라

문제 해결 아이디어

  • 오름차순 배열이다.
    • 합 중 가장 앞 인덱스 두개의 합이 가장 작다.
    • 합 중 가장 뒷 인덱스 두개의 합이 가장 크다.
      ➡️ 인덱스로 값이 target 과 비슷해지게 조절할 수 있다.

🧐 투포인터를 활용하자

의사 코드

  1. 왼쪽 인덱스와 오른쪽 인덱스를 가르키는 포인터를 선언한다.
  2. 각 포인터 인덱스가 가르키는 숫자의 합을 구한다.
  3. 합이 target과 같다. (조건)
    3-1. 포인터 인덱스들을 리턴한다.
  4. 합이 target보다 크다. (조건)
    4-1. 오른쪽 인덱스 값을 1 감소시킨다.
  5. 합이 target보다 작다. (조건)
    5-1. 왼쪽 인덱스 값을 1 증가시킨다.
left = 0
right = 마지막 인덱스
while(left < right){
	합 = numbers[left] + numbers[right]
    if(합 == target){
    	return 답
    }
   else if(합 > target){
    	right--
   } else {
   		left++
   } 
}

결과

전체 코드 github 링크

다른 풀이

public int[] twoSum(int[] nums, int target) {
	int l = 0, r = nums.length - 1;
	
	while (nums[l] + nums[r] != target) {
		if (nums[l] + nums[r] < target) l++;
		else r--;
	}

	return new int[] {l+1, r+1};
}

두 값의 합이 target 이 되는 인덱스가 반드시 존재한다는 조건을 잘 활용해서 나보다 훨씬 간결하게 코드를 작성했다.
나도 조건을 잘 살펴야할 것 같다

0개의 댓글