class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 初始化双指针，左指针指向数组起始（最小元素），右指针指向数组末尾（最大元素）
        left = 0
        right = len(numbers) - 1
        # 双指针循环，左指针小于右指针避免重复使用同一元素
        while left < right:
            # 计算当前双指针指向元素的和
            s = numbers[left] + numbers[right]
            # 找到目标和，返回从1开始的下标（题目要求）
            if s == target:
                return [left + 1, right + 1]
            # 和大于目标值，右指针左移，缩小和的大小
            elif s > target:
                right -= 1
            # 和小于目标值，左指针右移，增大和的大小
            else:
                left += 1
        # 若没有找到符合条件的两个数，返回空列表（题目隐含无此情况，但保证代码完整性）
        return []

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 排序：使数组有序，为双指针使用和去重提供前提
        nums.sort()
        # 存储最终结果的列表
        ans = []
        # 获取数组长度，用于循环边界控制
        n = len(nums)
        # 枚举第一个数（固定），遍历到n-2（保证后面有两个数组成三元组）
        for i in range(n - 2):
            x = nums[i]
            # 去重：当前数与前一个数相同，跳过，避免重复三元组
            if i > 0 and x == nums[i - 1]:
                continue
            # 优化1：最小的三个数之和已大于0，后续所有组合和都大于0，直接终止循环
            if x + nums[i + 1] + nums[i + 2] > 0:
                break
            # 优化2：当前数与最大的两个数之和仍小于0，当前数无法组成有效三元组，跳过
            if x + nums[-2] + nums[-1] < 0:
                continue
            # 初始化双指针，左指针在i+1（避免重复使用当前数），右指针在数组末尾
            j = i + 1
            k = n - 1
            # 双指针循环，左指针小于右指针避免重复使用元素
            while j < k:
                # 计算三元组的和
                s = x + nums[j] + nums[k]
                # 和大于0，右指针左移，缩小和的大小
                if s > 0:
                    k -= 1
                # 和小于0，左指针右移，增大和的大小
                elif s < 0:
                    j += 1
                # 和等于0，找到有效三元组
                else:
                    # 将有效三元组加入结果列表
                    ans.append([x, nums[j], nums[k]])
                    # 左指针右移，继续寻找其他可能的组合
                    j += 1
                    # 去重：左指针跳过重复元素
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    # 右指针左移，继续寻找其他可能的组合
                    k -= 1
                    # 去重：右指针跳过重复元素
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
        # 返回所有不重复的有效三元组
        return ans

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        ans = 0
        nums.sort()
        
        while left < right:
            if nums[left] + nums[right] >= target:
                right -= 1
            else:
                ans += right - left
                left += 1
        return ans

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        ans = math.inf
        n = len(nums)
        nums.sort()
        
        for i in range(n-2):
            left = i + 1
            right = n - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if abs(s - target) < abs(ans - target):
                    ans = s 
                if s == target:
                    return target
                elif s > target:
                    right -= 1
                else:
                    left += 1
        return ans

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = []

        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                l, r = j + 1, n - 1
                while l < r:
                    s = nums[i] + nums[j] + nums[l] + nums[r]
                    if s == target:
                        ans.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                        while l < r and nums[r] == nums[r + 1]:
                            r -= 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
        return ans

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        ans = 0
        for k in range(2, n):
            c = nums[k]
            i = 0
            j = k - 1
            while i < j:
                if nums[i] + nums[j] > c:
                    ans += j - i 
                    j -= 1
                else:
                    i += 1
        return ans