LeetCode 259 3 Sum Smaller

Given an array of n integers nums and a 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.

For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Challange
Solve it in O(n2) runtime

Difficulty
Medium

Analysis

Use similar algorithm with 3 Sum

Idea

Solutions

1. Cpp solution

   class Solution {
   public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int n = (int)nums.size()
        if(n < 3) return 0;
        sort(nums.begin(), nums.end());
        int cnt = 0;
        for (int i = 0; i < n - 2; i++){
            int begin = i + 1, end = n - 1;
            while(begin < end) {
                sum = nums[i] + nums[begin] + nums[end]
                if(sum < target) {
                    cnt += end - begin;
                    begin++;
                } else {
                    end--;
                }
            }
        }
        return cnt;
    }
   };
   

2. Go solution

func threeSumSmaller(nums []int, target int) int{
    n := len(nums)
    if n < 3 {
        return 0
    }
    sort.Ints(nums)
    var cnt int
    for i := 0; i < n - 2; i++ {
        begin, end := i + 1, n - 1
        for begin < end {
            sum := nums[i] + nums[begin] + nums[end]
            if sum < target {
                cnt += end - begin
                begin++
            } else {
                end--
            }
        }
    }
    return cnt
}

1. Python solution

class Solution(object):
    def threeSumSmaller(self, nums, target):
        nums.sort()
        cnt = 0
        for i in xrange(0, len(nums) - 2):
            if 3*nums[i] >= target:
                return cnt
            begin = i + 1
            end = len(nums) - 1
            while begin < end:
                sum = nums[i] + nums[begin] + nums[end] 
                if sum < target:
                    cnt += end - begin
                    begin += 1
                else:
                    end -= 1

        return cnt

Reference