443 · 两数之和 II

Difficulty

Medium

法2 排序 + 二分查找

思路

固定一个 nums[i] 值，然后去寻找左边满足 nums[j] + nums[i] > target 的最小的j，这样 nums[i] + nums[i:j] 的所有值都满足了，所以此时 res += i - j

O(nlogn) ,因为排序就是O(nlogn)的，其实双指针本来是O(n)的

题解


from typing import (
    List,
)

class Solution:
    """
    @param nums: an array of integer
    @param target: An integer
    @return: an integer
    """
    def two_sum2(self, nums: List[int], target: int) -> int:
        # write your code here
        nums.sort()
        left, right = 0, 1
        res = 0
        for i in range(1, len(nums)):
            l, r = 0, i-1
            while l <= r:
                m = l + (r - l) // 2
                if nums[m] + nums[i] > target:
                    r = m - 1
                else:
                    l = m + 1
            res += (i - l)
        return res

法1 排序 + 双指针

思路

使用双指针从两侧向中间遍历

- 利用单调性，可知若 nums[l] + nums[r] > target, 则 nums[l + k] + nums[r] > target (k >= 0)

- 每次计算答案时result += r - l 表示nums[l] 可以与 nums[l + 1 : r + 1] 这 r - l 个元素配对和大于 target

相当于是固定了 left指针

O(nlogn)，排序是O(nlogn),查找也是O(nlogn)d

题解


class Solution:

    """
    @param nums: an array of integer
    @param target: An integer
    @return: an integer
    """

    def twoSum2(self, nums, target):
        n = len(nums)
        nums.sort()
        result = 0
        l, r = 0, n - 1
        while l < r:
            #若l指向元素与r指向元素的和不大于target
            if nums[l] + nums[r] <= target:
                l += 1
            #否则，nums[l]可以与nums[l + 1 : r + 1]这r - l个元素配对
            else:
                result += r - l
                r -= 1
        return result

443 · 两数之和 II - LintCode

法2 排序 + 二分查找

法1 排序 + 双指针