{"id":10070,"date":"2023-08-23T18:09:34","date_gmt":"2023-08-24T01:09:34","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10070"},"modified":"2023-08-23T18:20:43","modified_gmt":"2023-08-24T01:20:43","slug":"leetcode-2824-count-pairs-whose-sum-is-less-than-target","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2824-count-pairs-whose-sum-is-less-than-target\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2824.\u00a0Count Pairs Whose Sum is Less than Target"},"content":{"rendered":"\n

Given a 0-indexed<\/strong> integer array nums<\/code> of length n<\/code> and an integer target<\/code>, return the number of pairs<\/em>(i, j)<\/code>where<\/em>0 <= i < j < n<\/code>and<\/em>nums[i] + nums[j] < target<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [-1,1,2,3,1], target = 2\nOutput:<\/strong> 3\nExplanation:<\/strong> There are 3 pairs of indices that satisfy the conditions in the statement:\n- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target\n- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target \n- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target\nNote that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [-6,2,5,-2,-7,-1,3], target = -2\nOutput:<\/strong> 10\nExplanation:<\/strong> There are 10 pairs of indices that satisfy the conditions in the statement:\n- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target\n- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target\n- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target\n- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target\n- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target\n- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target\n- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target\n- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target\n- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target\n- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length == n <= 50<\/code><\/li>
  • -50 <= nums[i], target <= 50<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: Brute force<\/strong><\/h2>\n\n\n\n
    Enumerate all pairs.<\/p>\n\n\n\n
    Time complexity: O(n2<\/sup>)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countPairs(vector& nums, int target) {\n    const int n = nums.size();\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      for (int j = i + 1; j < n; ++j)\n        ans += nums[i] + nums[j] < target;\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Two Pointers<\/strong><\/h2>\n\n\n\n
    Sort the numbers.<\/p>\n\n\n\n
    Use two pointers i, and j.
    Set i to 0 and j to n - 1.
    while (nums[i] + nums[j] >= target) --j
    then we have nums[i] + nums[k] < target (i < k <= j), in total (j - i) pairs.
    ++i, move to the next starting number.
    Time complexity: O(nlogn + n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countPairs(vector& nums, int target) {\n    const int n = nums.size();\n    sort(begin(nums), end(nums));\n    int ans = 0;\n    for (int i = 0, j = n - 1; i < n; ++i) {\n      while (j >= i && nums[i] + nums[j] >= target) --j;      \n      ans += max(0, j - i);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs(i, j)where0 <= i < j < nandnums[i] + nums[j] < target. Example 1: Input: nums…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,222,175],"class_list":["post-10070","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-easy","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10070","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10070"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10070\/revisions"}],"predecessor-version":[{"id":10076,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10070\/revisions\/10076"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10070"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10070"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}