Skip to content

259. 3Sum Smaller πŸ”’

Description

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

 

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2:

Input: nums = [], target = 0
Output: 0

Example 3:

Input: nums = [0], target = 0
Output: 0

 

Constraints:

  • n == nums.length
  • 0 <= n <= 3500
  • -100 <= nums[i] <= 100
  • -100 <= target <= 100

Solutions

Solution 1: Sorting + Two Pointers + Enumeration

Since the order of elements does not affect the result, we can sort the array first and then use the two-pointer method to solve this problem.

First, we sort the array and then enumerate the first element \(\textit{nums}[i]\). Within the range \(\textit{nums}[i+1:n-1]\), we use two pointers pointing to \(\textit{nums}[j]\) and \(\textit{nums}[k]\), where \(j\) is the next element of \(\textit{nums}[i]\) and \(k\) is the last element of the array.

  • If \(\textit{nums}[i] + \textit{nums}[j] + \textit{nums}[k] < \textit{target}\), then for any element \(j \lt k' \leq k\), we have \(\textit{nums}[i] + \textit{nums}[j] + \textit{nums}[k'] < \textit{target}\). There are \(k - j\) such \(k'\), and we add \(k - j\) to the answer. Next, move \(j\) one position to the right and continue to find the next \(k\) that meets the condition until \(j \geq k\).
  • If \(\textit{nums}[i] + \textit{nums}[j] + \textit{nums}[k] \geq \textit{target}\), then for any element \(j \leq j' \lt k\), it is impossible to make \(\textit{nums}[i] + \textit{nums}[j'] + \textit{nums}[k] < \textit{target}\). Therefore, we move \(k\) one position to the left and continue to find the next \(k\) that meets the condition until \(j \geq k\).

After enumerating all \(i\), we get the number of triplets that meet the condition.

The time complexity is \(O(n^2)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, n = 0, len(nums)
        for i in range(n - 2):
            j, k = i + 1, n - 1
            while j < k:
                x = nums[i] + nums[j] + nums[k]
                if x < target:
                    ans += k - j
                    j += 1
                else:
                    k -= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = 0, n = nums.length;
        for (int i = 0; i + 2 < n; ++i) {
            int j = i + 1, k = n - 1;
            while (j < k) {
                int x = nums[i] + nums[j] + nums[k];
                if (x < target) {
                    ans += k - j;
                    ++j;
                } else {
                    --k;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        ranges::sort(nums);
        int ans = 0, n = nums.size();
        for (int i = 0; i + 2 < n; ++i) {
            int j = i + 1, k = n - 1;
            while (j < k) {
                int x = nums[i] + nums[j] + nums[k];
                if (x < target) {
                    ans += k - j;
                    ++j;
                } else {
                    --k;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func threeSumSmaller(nums []int, target int) (ans int) {
    sort.Ints(nums)
    n := len(nums)
    for i := 0; i < n-2; i++ {
        j, k := i+1, n-1
        for j < k {
            x := nums[i] + nums[j] + nums[k]
            if x < target {
                ans += k - j
                j++
            } else {
                k--
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function threeSumSmaller(nums: number[], target: number): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n - 2; ++i) {
        let [j, k] = [i + 1, n - 1];
        while (j < k) {
            const x = nums[i] + nums[j] + nums[k];
            if (x < target) {
                ans += k - j;
                ++j;
            } else {
                --k;
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumSmaller = function (nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n - 2; ++i) {
        let [j, k] = [i + 1, n - 1];
        while (j < k) {
            const x = nums[i] + nums[j] + nums[k];
            if (x < target) {
                ans += k - j;
                ++j;
            } else {
                --k;
            }
        }
    }
    return ans;
};

Comments