259. 3Sum Smaller

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.

• Time : O(n^2)
• Space : O(1)

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int res = 0;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++) {
            int j = i + 1, k = nums.size() - 1;
            while(j < k) {
                while(j < k and nums[i] + nums[j] + nums[k] >= target) k--;
                res += k - j;
                j++;
            }
        }
        return res;
    }
};

• Time : O(n^2logn)

• Space : O(1)

  class Solution {
  public:
      int threeSumSmaller(vector<int>& nums, int target) {
          int res = 0;
          for(int i = nums.size() - 3; i >= 0; --i) {
              sort(nums.begin() + i + 1, nums.end());
              for(int j = i + 1; j < nums.size() - 1; j++) {
                  int t = target - nums[i] - nums[j];
                  auto it = lower_bound(nums.begin() + j + 1, nums.end(), t);
                  if(it == nums.begin() + j + 1) break;
                  res += it - (nums.begin() + j + 1);
              }
          }
          return res;
      }
  };

• Time : O(n^2)

• Space : O(n)

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        map<int, int> counter;
        int res = 0;
        for(int i = nums.size() - 3; i >= 0; --i) {
            for(int j = i + 1, k = i + 2; k < nums.size(); k++) {
                counter[nums[j] + nums[k]]++;
            }
            auto ed = counter.lower_bound(target - nums[i]);
            for(auto it = counter.begin(); it != ed; it++) {
                res += it->second;
            }
        }
        return res;
    }
};