3Sum Smaller

还是类似3sum的三指针，不过内部的双指针遍历时可以发现上界下移之后是不用再倒回的，因为我们这里找的是小的

class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        n = len(nums)
        base = 0
        res = 0
        while base <= n - 3:
            a = nums[base]
            start, end = base + 1, n - 1
            while start <= end - 1:
                b, c = nums[start], nums[end]
                if a + b + c >= target:
                    end -= 1
                else:
                    res += (end - start)
                    start += 1
            base +=1 
        return res

还可以利用二分每次找最后一个值的位置

class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        res = 0
        n = len(nums)

        for i in xrange(n - 2):
            a = nums[i]
            for j in xrange(i + 1, n - 1):
                index = bisect.bisect_left(nums, target - a - nums[j], lo=j, hi=n)
                if index > j + 1:
                    res += (index - j - 1)

        return res