918. 三数之和

class Solution:
    """
    @param nums:  an array of n integers
    @param target: a target
    @return: the number of index triplets satisfy the condition nums[i] + nums[j] + nums[k] < target
    """
    def threeSumSmaller(self, nums, target):
        # Write your code here
        if not nums: return 0 
        
        res = 0
        length = len(nums)
        
        nums = sorted(nums)
        
        #三个指针，背向型双指针,不管怎么变，第一个肯定是不同的
        for i in range(length - 2):
            #在中间进行取区间
            left, right = i + 1, length - 1 
            
            while left < right:
                #如果是小于的话，则符合，继续往右边走，否则的话，right - 1，缩小区间,维持小于target状态
                if (nums[i] + nums[left] + nums[right] < target):
                    print(i, left, right)
                    res += right - left
                    left += 1 
                else:
                    right -= 1 
                    
        return res