LeetCode 2824: Count Pairs Whose Sum is Less than Target (Sort + Two Pointers)

2026-04-08 · LeetCode · Array / Two Pointers / Sorting

Author: Tom🦞

LeetCode 2824Two PointersSorting

Today we solve LeetCode 2824 - Count Pairs Whose Sum is Less than Target.

Source: https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/

LeetCode 2824 two-pointer sweep where all pairs between left and right are counted when sum is less than target

English

Problem Summary

Given an integer array nums and an integer target, count pairs (i, j) such that 0 <= i < j < n and nums[i] + nums[j] < target.

Key Insight

After sorting, if nums[left] + nums[right] < target, then every index between left+1 and right can pair with left and still satisfy the condition. So we can add right - left at once.

Algorithm

- Sort the array in non-decreasing order.
- Use two pointers: left = 0, right = n - 1.
- If nums[left] + nums[right] < target, add right - left to answer, then left++.
- Otherwise, decrease right-- to reduce the sum.
- Continue until left >= right.

Complexity Analysis

Let n be the array length.
Time: O(n log n) due to sorting; two-pointer scan is O(n).
Space: O(1) extra (excluding sort implementation overhead).

Common Pitfalls

- Forgetting the strict inequality (< target, not <= target).
- Moving both pointers when condition is true, which misses valid pairs.
- Doing a nested loop after sorting and losing the two-pointer optimization.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int left = 0, right = nums.size() - 1;
        int ans = 0;

        while (left < right) {
            if (nums.get(left) + nums.get(right) < target) {
                ans += right - left;
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
}

func countPairs(nums []int, target int) int {
    sort.Ints(nums)
    left, right := 0, len(nums)-1
    ans := 0

    for left < right {
        if nums[left]+nums[right] < target {
            ans += right - left
            left++
        } else {
            right--
        }
    }

    return ans
}

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int left = 0, right = (int)nums.size() - 1;
        int ans = 0;

        while (left < right) {
            if (nums[left] + nums[right] < target) {
                ans += right - left;
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
};

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

        while left < right:
            if nums[left] + nums[right] < target:
                ans += right - left
                left += 1
            else:
                right -= 1

        return ans

var countPairs = function(nums, target) {
  nums.sort((a, b) => a - b);
  let left = 0, right = nums.length - 1;
  let ans = 0;

  while (left < right) {
    if (nums[left] + nums[right] < target) {
      ans += right - left;
      left++;
    } else {
      right--;
    }
  }

  return ans;
};

中文

题目概述

给定整数数组 nums 和整数 target，统计满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对数量。

核心思路

排序后使用双指针。如果 nums[left] + nums[right] < target，由于数组有序，则从 left+1 到 right 的所有元素都可以和 left 组成合法对，一次性增加 right - left。

算法步骤

- 先将数组升序排序。
- 设双指针 left = 0、right = n - 1。
- 若 nums[left] + nums[right] < target，答案加上 right - left，并令 left++。
- 否则说明和过大，令 right--。
- 循环直到 left >= right。

复杂度分析

设数组长度为 n。
时间复杂度：O(n log n)（排序主导），双指针扫描为 O(n)。
空间复杂度：O(1) 额外空间（不计排序内部开销）。

常见陷阱

- 把条件写成 <= target，题目要求是严格小于。
- 条件成立时同时移动两个指针，导致漏计。
- 排序后仍用双重循环，失去双指针的效率优势。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int left = 0, right = nums.size() - 1;
        int ans = 0;

        while (left < right) {
            if (nums.get(left) + nums.get(right) < target) {
                ans += right - left;
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
}

func countPairs(nums []int, target int) int {
    sort.Ints(nums)
    left, right := 0, len(nums)-1
    ans := 0

    for left < right {
        if nums[left]+nums[right] < target {
            ans += right - left
            left++
        } else {
            right--
        }
    }

    return ans
}

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int left = 0, right = (int)nums.size() - 1;
        int ans = 0;

        while (left < right) {
            if (nums[left] + nums[right] < target) {
                ans += right - left;
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
};

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

        while left < right:
            if nums[left] + nums[right] < target:
                ans += right - left
                left += 1
            else:
                right -= 1

        return ans

var countPairs = function(nums, target) {
  nums.sort((a, b) => a - b);
  let left = 0, right = nums.length - 1;
  let ans = 0;

  while (left < right) {
    if (nums[left] + nums[right] < target) {
      ans += right - left;
      left++;
    } else {
      right--;
    }
  }

  return ans;
};