[java/python3] leetcode 259. 3Sum Smaller

문제

https://leetcode.com/problems/3sum-smaller/description/

3Sum Smaller - LeetCode

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

 

풀이

배열의 길이가 최대 3500 임으로, O(N^3) 은 1억을 훨씬 넘기기 때문에, O(N^2 ) 을 최대로 해야한다.

투포인터로 접근하였다. 일단 문제에서 구해야할 차원을 축소하기 위해서, for문으로 i, j , k 3 가지 파라미터를 j , k 두 가지 파라미터로 축소한다.

        for i in range(len(nums)-2):
            ans += self.helper(nums, target - nums[i], i+1)

그 다음 양 쪽 끝에서 움직이는 포인터 Left, Right 를 만들어서 양쪽 범위의 합에 따라 증감을 해준다

       while left < right:
            if nums[left] + nums[right] < t :
                ret += right - left
                left += 1
            else:
                right -= 1

여기서 nums[left] + nums[right] < t 라면 , 현재 left 일때. 제일 큰 right 랑 더했을 때 target 보다 작음으로 right 경우의 수를 더해준다. 

right 의 경우의 수가 right - left 만큼 있음으로 그 수만큼 카운팅 해준다.

target 보다 크면 right 를 왼쪽으로 이동시킨다. 

 

코드

파이썬

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = 0
        for i in range(len(nums)-2):
            ans += self.helper(nums, target - nums[i], i+1)
        return ans
        
    def helper(self, nums: List[int], t: int, start: int)->int:
        left = start
        right = len(nums)-1
        ret = 0
        while left < right:
            if nums[left] + nums[right] < t :
                ret += right - left
                left += 1
            else:
                right -= 1

        return ret

자바

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }

    private int twoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        int left = startIndex;
        int right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] < target) {
                sum += right - left;
                left++;
            } else {
                right--;
            }
        }
        return sum;
    }
}