Triangle Count

刷题刷到现在这个程度，这个题应该是第一眼就要看出来要的是一个O(n^2)的解，所以双指针的思路也是应该马上蹦出来的，不过这个题并不像一般的n^2的双指针应用的是3sum那道题的思维，而是用一个for循环固定上界，然后双指针在上界范围内滚动，这样可以确保所有当前范围内的有效解都被收入，如果以for循环为下界也就是3sum的做法的话，无论如何处理指针都会有漏掉的解，也是因为这种从小范围搜索到逐渐扩大范围搜索的思路我觉得很像动态规划，也是这道题和一般指针问题的不同之处，很有参考价值

class Solution:
    # @param S: a list of integers
    # @return: a integer
    def triangleCount(self, nums):
        # write your code here
        n = len(nums)
        res = 0
        nums.sort()

        for i in xrange(n):
            left, right = 0, i - 1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    res += (right - left)
                    right -= 1
                else:
                    left += 1

        return res