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?
Analyse: this problem only consider the index, rather than the value. Thus, we don‘t need to avoid duplicate values.
Runtime: 13ms
1 class Solution { 2 public: 3 int threeSumSmaller(vector<int>& nums, int target) { 4 if (nums.size() < 3) return 0; 5 6 sort(nums.begin(), nums.end()); 7 int result = 0; 8 for (int i = 0; i < nums.size() - 2; i++) { 9 int k = nums.size() - 1; 10 for (int j = i + 1; j < k; ) { 11 if (nums[i] + nums[j] + nums[k] < target) { 12 result += (k - j); 13 j++; 14 } 15 else k--; 16 } 17 } 18 return result; 19 } 20 };
原文：http://www.cnblogs.com/amazingzoe/p/5880079.html