259. 3Sum Smaller

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.

 

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2:

Input: nums = [], target = 0
Output: 0

Example 3:

Input: nums = [0], target = 0
Output: 0

 

Constraints:

• n == nums.length
• 0 <= n <= 3500
• -100 <= nums[i] <= 100
• -100 <= target <= 100

---

# https://leetcode.com/problems/3sum-smaller/
'''
1. 아이디어 :
    1) 2중 포문안에, num1을 고정시키고, 투포인터로 num2, num3을 찾는다. num3를 감소시키다가
    num2 + num3 < target - num1 이 되는 순간, break를 걸고 rp와 lp의 거리를 ans에 더해준다.
2. 시간복잡도 :
    1) O(logn) + O(n^2) * O(logN)= O(n^2logN)
    - sort * 2중포문 * 투포인터
3. 자료구조 :
    1) 배열

'''
class Solution:
    def threeSumSmaller(self, n: List[int], target: int) -> int:
        ans=0
        n.sort()
        for j in range(len(n)-2):
            t=target-n[j]
            rp=len(n)-1
            for i in range(j+1,len(n)-1):
                lp=i
                while lp<rp:
                    if n[lp]+n[rp]>=t:
                        rp-=1
                    elif n[lp]+n[rp]<t:
                        print(j,lp,rp)
                        ans+=rp-lp
                        break

        return ans