[LeetCode] 1099. Two Sum Less Than K

1099. Two Sum Less Than K

Easy

Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.

 

Example 1:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

Example 2:

Input: nums = [10,20,30], k = 15
Output: -1
Explanation: In this case it is not possible to get a pair sum less that 15.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 1000
• 1 <= k <= 2000

---

문제 풀이

• 주어진 배열에서 숫자 두개를 더한 값이 K보다 작을때 가장 큰 값을 구해야한다.

부루트 포스

• 배열을 각각 더해보면서 K 값보다 작을때 최대값을 저장한다.
• 정렬 + 투포인터
• 배열을 정렬하고 배열의 양끝에서 인덱스를 옮기면서 값을 계산한다.
• 만약 두개의 숫자를 더한 값이 K보다 작다면 최대값을 구하고 왼쪽 포인터를 하나 올린다. 
• 정렬이 되어있기 때문에 왼쪽 포인터를 오른쪽으로 옮기면 숫자가 커져서 합도 증가할 것이다.

바이너리 서치 

• 투포인터와 비슷한 로직이다. 
• 배열을 먼저 정렬한다. 
• 가장 작은 값부터 진행하는데, 값을 K에서 뺀것을 Lower boundery 바이너리 서치로 위치를 검색한다. 
• bisect_left를 사용하면되는데, K에서 현재 위치의 값을 뺀것에 가장 가까우면서 왼쪽 위치의 값을 찾는다, 즉, K - nums[i] 보다 작은 값을 찾게 된다. 
• (bisect_right는 반대이다.)
• 만약 j 가 i 보다 크면 최대값을 구해준다. 
• (이진 탐색의 시작 위치를 정해주었어도 i 보다 작은 인덱스를 결과로 가져올 수 있기 때문이다.)

카운팅 소트

• 숫자의 최대값인 1000까지 빈 배열을 만든다. 
• 이 배열은 숫자의 개수를 저장할 배열이다.
• 1부터 최대 값인 1000까지 진행을 하는데 투포인터처럼 양끝에서 시작한다.
• 만일 두개의 값의 합이 K보다 같거나 크면 오른쪽 포인터를 하나 줄여준다. 
• 혹은 오른쪽 포인터의 값이 배열에 존재하지 않으면 오른쪽 포인터를 하나 줄여준다.
• 만일 두 값의 합이 K보다 작을때, l이 r보다 작고 배열에 l 숫자가 존재하면 맥스 값을 설정한다.
• 반대로 l 과 r 값이 같을때는 l의 개수가 1개 초과이어야한다.

소스 코드

브루트 포스 O(N^2)

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        m = -1
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                t = nums[i] + nums[j]
                if t < k:
                    m = max(m, t)
        return m

정렬 + 투포인터 O(NlogN)

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        m = -1
        l, r = 0, len(nums) - 1
        while l < r:
            total = nums[l] + nums[r]
            if total < k:
                m = max(m, total)
                l += 1
            else:
                r -= 1
        return m

바이너리 서치 O(NlogN)

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        m = -1
        nums.sort()
        for i in range(len(nums)):
        # nums은 배열, k - nums[i]는 찾을 값, i + 1은 시작점
            j = bisect_left(nums, k - nums[i], i + 1) - 1
            if j > i:
                m = max(m, nums[i] + nums[j])
        return m

카운팅 소트 O(N + M) M은 입력으로 들어온 배열의 길이이다.

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        m = -1
        cnt = [0] * 1001
        for num in nums:
            cnt[num] += 1
        l, r = 1, 1000
        while l <= r:
            if l + r >= k or cnt[r] == 0:
                r -= 1
            else:
                if l < r and cnt[l] > 0 or l == r and cnt[l] > 1:
                    m = max(m, l + r)
                l += 1
        return m