259. 3Sum Smaller

leetcode medium

#array#csharp#leetcode#medium#search#sort#two-pointers

Task

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

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]

C# solution

matched/original

using System;
public class Solution {
    public int ThreeSumSmaller(int[] nums, int target) {
        Array.Sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.Length - 2; i++) {
            sum += TwoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }
    private int TwoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        for (int i = startIndex; i < nums.Length - 1; i++) {
            int j = BinarySearch(nums, i, target - nums[i]);
            sum += j - i;
        }
        return sum;
    }
    private int BinarySearch(int[] nums, int startIndex, int target) {
        int left = startIndex;
        int right = nums.Length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ThreeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size() - 2; i++) {
            sum += TwoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }
    private int TwoSumSmaller(vector<int>& nums, int startIndex, int target) {
        int sum = 0;
        for (int i = startIndex; i < nums.size() - 1; i++) {
            int j = BinarySearch(nums, i, target - nums[i]);
            sum += j - i;
        }
        return sum;
    }
    private int BinarySearch(vector<int>& nums, int startIndex, int target) {
        int left = startIndex;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

Java solution

matched/original

import java.util.Arrays;

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }

    private int twoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        for (int i = startIndex; i < nums.length - 1; i++) {
            int j = binarySearch(nums, i, target - nums[i]);
            sum += j - i;
        }
        return sum;
    }

    private int binarySearch(int[] nums, int startIndex, int target) {
        int left = startIndex;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

JavaScript solution

matched/original

class Solution {
    threeSumSmaller(nums, target) {
        nums.sort((a, b) => a - b)
        let sum = 0
        for (let i = 0; i < nums.length - 2; i++) {
            sum += this.twoSumSmaller(nums, i + 1, target - nums[i])
        }
        return sum
    }

    twoSumSmaller(nums, startIndex, target) {
        let sum = 0
        for (let i = startIndex;

Python solution

matched/original

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        sum_count = 0
        for i in range(len(nums) - 2):
            sum_count += self.twoSumSmaller(nums, i + 1, target - nums[i])
        return sum_count

    def twoSumSmaller(self, nums: List[int], startIndex: int, target: int) -> int:
        sum_count = 0
        for i in range(startIndex, len(nums) - 1):
            j = self.binarySearch(nums, i, target - nums[i])
            sum_count += j - i
        return sum_count

    def binarySearch(self, nums: List[int], startIndex: int, target: int) -> int:
        left, right = startIndex, len(nums) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid - 1
        return left

Go solution

matched/original

import "sort"

func threeSumSmaller(nums []int, target int) int {
    sort.Ints(nums)
    sum := 0
    for i := 0; i < len(nums)-2; i++ {
        sum += twoSumSmaller(nums, i+1, target-nums[i])
    }
    return sum
}

func twoSumSmaller(nums []int, startIndex int, target int) int {
    sum := 0
    for i := startIndex; i < len(nums)-1; i++ {
        j := binarySearch(nums, i, target-nums[i])
        sum += j - i
    }
    return sum
}

func binarySearch(nums []int, startIndex int, target int) int {
    left, right := startIndex, len(nums)-1
    for left < right {
        mid := (left + right + 1) / 2
        if nums[mid] < target {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

Explanation

Algorithm

1️⃣

Отсортируйте массив nums.

2️⃣

Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3️⃣

В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎