LeetCode Q259: 3Sum 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]

Follow up:
Could you solve it in O(n2) runtime?

Solution:

Use two technique of two pointers. The outter loop loop over all elements in the sorted array. in the loop, use two pointers to decide the count. When using two pointers. No need to iterate over all valid case. Because once we find the first valid pair, we can just count how many numbers are there in between this pair. 

On extra trick is to use early stop when v0 > target/3.

	class Solution {
	public:
	int threeSumSmaller(vector<int>& nums, int target) {
	sort(nums.begin(), nums.end());
	int count=0;
	for(int i=0; i<nums.size(); i++){
	int v0=nums[i];
	int p1=i+1;
	int p2=nums.size()-1;
	if(v0>target/3.0)
	return count;
	while(p1<p2){
	int v1=nums[p1];
	int v2=nums[p2];
	if(v0+v1+v2<target){
	count=count+p2-p1;
	p1++;
	}else
	p2--;
	}
	}
	return count;
	}
	};

view raw Q2593SumSmaller.cpp hosted with ❤ by GitHub

Round 2 Solution

	class Solution {
	public:
	void helper(vector<int>& nums, int& res, int target, int curSum, int idx, int k){
	if(k==0){
	res = curSum<target? res+1:res;
	return;
	}
	for(int i=idx; i<nums.size(); i++){
	curSum = curSum+nums[i];
	helper(nums, res, target, curSum, i+1, k-1);
	curSum = curSum-nums[i];
	}
	}
	int threeSumSmaller(vector<int>& nums, int target) {
	int res=0;
	int curSum=0;
	if(nums.empty())
	return res;
	helper(nums, res, target, curSum, 0, 3);
	return res;
	}
	};

view raw Q259Rnd2.cpp hosted with ❤ by GitHub