clueless coding // TODO: be smarter

LeetCode 259. 3 Sum Smaller: C++ Solution



Problem Statement


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.

Function Signature (C++):
  int threeSumSmaller(vector<int>& nums, int target)

Inputs:
  nums = [-2, 0, 1, 3]
  target = 2

Outputs:
  2

Two triplets with sums less than 2 can be created:
  [-2, 0, 1]
  [-2, 0, 3]



TL;DR Code Solution


int threeSumSmaller(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());

    int count = 0;
    for (int i = 0; i < (int)nums.size() - 1; i++) {
        int pin = nums[i];
        int right = (int)nums.size() - 1;
        int left = i + 1;
        while (left < right) {
            int sum = pin + nums[left] + nums[right];
            if (sum < target) {
                count += right - left;
                left++;
            }
            else {
                right--;
            }
        }
    }
    return count;
}